Abstract:
A system for transparently transporting m synchronous data streams as an aggregate data stream on a single channel of a Wave Division Multiplexed (WDM) optical link without pointer processing uses m unique encoding schemes to enable recovery of the respective m data streams from the aggregate data stream. The encoding schemes are preferably self-inverting. The respective m data streams are parsed into data units and encoded. The data units are then interleaved to form the aggregate data stream. Recovery is accomplished using a reverse process.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This is the first application filed for the present invention. 
     MICROFICHE APPENDIX 
     Not applicable. 
     TECHNICAL FIELD 
     The present invention relates to the multiplexing of SONET/SDH data streams and, in particular, to a method of interleaving tributary data streams and recovering the tributary data streams, using unique, independent encoding schemes. 
     BACKGROUND OF THE INVENTION 
     Optical fiber, because of its data transfer capacity and reliability, has become a commonly used medium for data transport. Synchronous Optical NETwork (SONET) and Synchronous Digital Hierarchy (SDH) standards are used to enable network devices, made by different manufacturers, to receive and transmit data streams through optical networks. Certain optical fibers have the capacity to convey independent data streams on multiple wavelength channels. The transmission of data streams onto different wavelength channels of a single fiber is familiar to those skilled in the art, and referred to as Wave Division Multiplexing (WDM). 
     The data stream with a lowest density defined by current SONET standards is a stream of frames transmitted every 125 microseconds. Each frame includes three 9-byte columns of transport overhead and 87 9-byte columns of payload. This least dense SONET stream is called a Synchronous Transport Signal (STS-)1. A stream of STS-n frames convey n byte interleaved columns of STS-1 frames respectively, at the same rate of 8000 frames/s. For example, the first nine 9-byte columns of an STS-3 frame are transport overhead, and the remaining 261 columns are referred to as the Synchronous Payload Container. The transport overhead consists of section overhead, as defined by the SONET standard. 
     The first bytes of the an STS-1 frame are A1 and A2 bytes. These bytes are used to detect the beginning of frames, which permits SONET devices to parse SONET frames into constituent bytes. 
     The SONET standard defines the structure of a the frames, and the key to extracting data from the frames. A set of virtual tributaries (VTs) that make up the payload of a frame are indexed by pointer fields in the section overhead. The SONET standard also provides a protocol for producing higher bit-rate streams from STS-1 frames m Synchronous Transport Signal (STS)-n frames can be byte interleaved to produce an STS-(n×m) data stream, or can be concatenated to produce an STS-(n×m)c data stream. The transport, section, line and path overheads of higher bit-rate streams are also defined by the SONET standard. The section and line overhead of higher bit rate SONET frames are not identical to those of the constituent frames, and so when an STS-(n×m) data stream is formed, the overhead of the component data streams must be replaced. The byte interleaving and replacing of section and line overhead is referred to as “reframing”. 
     SONET signals are received by a class of SONET network elements (which includes line and section terminating equipment and routers), and the beginning of a SONET frame is detected by A1 and A2 byte filters. 
     The SDH protocol is very similar to the SONET protocol, but the two are not compatible to an extent that network elements adapted to propagate or terminate frames can be interchangeably used for either protocol. Consequently, if SONET frames are to be converted to SDH frames, or vice versa, a complex reformatting process is required. An example of a reformatting process is described in Assignee&#39;s co-pending U.S. patent application Ser. No. 09/494,518 which was filed on Jan. 31, 2000 and entitled METHOD AND APPARATUS FOR CROSS-CONNECTING DATA STREAMS WITH EFFICIENT MEMORY UTILIZATION AND TRANSPARENT PROTOCOL CONVERSION. 
     As is well known in the art, the speed of data transmission over optical fiber has been increasing at a steady and rapid rate. Consequently, as new high-speed equipment is connected into optical networks, it is often desirable to multiplex lower speed data streams for transport across the network in order to take advantage of the transport capacity of high-speed links. This gives rise to certain problems, however. First, in order to multiplex data streams in either SONET or SHD format, the frames must be pointer processed and reformatted as described above. The pointer processing changes certain frame header information, however, and this is not always acceptable to transport service customers. Second, SONET and SHD frames cannot be multiplexed together because of well understood incompatibilities between the two protocols. 
     It is therefore desirable to provide a method and apparatus that permits a plurality of low-speed data streams to be multiplexed onto a high-speed data channel without pointer processing, so that the multiplexing demultiplexing process is completely transparent to transport service customers. It is also desirable to provide a method and apparatus that permits synchronous data streams that conform to different protocols to be transparently multiplexed together without protocol conversion or pointer processing. 
     SUMMARY OF THE INVENTION 
     It is therefore an object of the invention to provide a method and apparatus for multiplexing/demultiplexing synchronous data streams in either SONET or SDH protocol, or any combination of the two protocols. 
     It is a further object of the invention to provide a method and apparatus for transparently multiplexing/demultiplexing synchronous data streams without pointer processing or protocol conversion. 
     Accordingly, the invention provides a method and system for encoding and multiplexing source data streams to form an aggregate data stream that is demultiplexed into component data streams using a self-inverting encoding scheme. 
     This is accomplished using a set of self-inverting encoding schemes, one for each of the data streams. The self-inverting encoding schemes are applied to the respective data streams. Each of the self-inverting encoding schemes must adhere to certain criteria. First, the encoding schemes of any given set must be unique. Second, the framing bytes of one data stream encoded by the encoding scheme associated with that stream must not, when decoded by any one of the other data streams, be identical to a framing byte of the one of the other data streams. The restriction of independence of a set of encoding schemes is ensured if the operation of any one of the set of encoding schemes does not influence the operation of the others in the set. 
     The method begins with parsing each of the m synchronous data streams into data units. This is accomplished by detecting respective framing bytes of each data stream. The data units of respective synchronous data streams are encoded using a respective encoding scheme, and then the encoded data units are interleaved to produce a serialized aggregate data stream. 
     The recovery of any one of the m synchronous data streams is performed by copying the aggregate data stream and applying a decoding scheme to data units of the copy of the aggregate data stream. The decoded data stream is then passed to a framer, which detects one or more framing bytes. After the framing bytes are detected, the remaining data units are recovered using a simple counting process in which every m th  data unit is selected to recover the one of the m synchronous data streams. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     Further features and advantages of the present invention will become apparent from the following detailed description, taken in combination with the appended drawings, in which: 
     FIG. 1 is a schematic diagram of functional components of an embodiment of the present invention; 
     FIG. 2 is a schematic diagram of an example of the functioning of the encoding and interleaving aspect of an embodiment of the invention; 
     FIG. 3 illustrates an example of the functioning of the decoding and collating aspect of an embodiment of the invention; and 
     FIG. 4 is a schematic diagram of encoding/decoding schemes that may be used to practice the method in accordance with the invention. 
    
    
     It will be noted that throughout the appended drawings, like features are identified by like reference numerals. 
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     The invention involves applying a respective encoding scheme to data units of each of m data streams, interleaving the encoded data units of the m data streams to form an aggregate data stream. Decoding schemes that invert the encoding schemes are then applied to respective copies of the aggregate data stream. De-interleaving is accomplished by selecting only data units that belong to the respective decoded data streams by selecting every m th  byte from each data stream after frame header bytes are located. 
     FIG. 1 is a schematic diagram of an embodiment of the present invention. Four synchronous data streams  10   a - 10   d  are received by respective data unit parsers  12   a - 12   d . The data unit parsers  12   a - 12   d  include an elastic store for byte-aligning the synchronous data streams  10   a - 10   d . The data unit parsers  12   a - 12   d  also include framing byte detectors for detecting A1/A2 framing bytes of SONET/SDH frames. Once the A1/A2 bytes are located, the respective data streams  10   a - 10   d  are parsed into fixed-length data units (1 byte, for example). After the respective data streams  10   a - 10   d  have been parsed into data units, their component data units are encoded one at a time by encoders  14   a - 14   d  using unique encoding schemes, as will be explained below in more detail. The output of the encoders  14   a - 14   d  is passed to a multiplexer  16  that interleaves the respective data units to form an aggregate data stream  17 . 
     Recovering the synchronous data streams involves reproducing the aggregate data stream in deserializers  18   a - 18   d  to produce four copies. The deserializers  18   a - 18   d  divide the aggregate data stream  17  into data words that are divided into data units and passed to a respective decoder  20   a - 20   d . Each decoder  20   a - 20   d  decodes the data units of the data stream using a decoding scheme adapted to revert a corresponding one of the encoding schemes. The four decoded aggregate data streams are passed to data unit collators  22   a - 22   d , which byte align and then collate the respective data streams. The collators  22   a - 22   d  select data units from the respective aggregate data streams, starting with the A1 byte. The selection is governed by the number m of synchronous data streams  10   a - 10   d  in the aggregate data stream  17 . After the A1 byte is detected and selected, every m th  data unit is selected from the aggregate data stream and collated to from a respective one of the recovered synchronous data streams  10   a - 10   d.    
     As will be understood by those skilled in the art, certain restrictions apply to the synchronous data streams  10   a - 10   d . For example, the four synchronous data streams  10   a - 10   d  must all have the same bit rate. The data streams must also be synchronized at the same frequency, and a beginning of each frame is indicated by A1/A2 framing bytes, which is the case for SONET/SDH data streams. There is no requirement, however, that the synchronous data streams be in the same format. Any combination of SONET and SDH data streams can be multiplexed together. 
     FIG. 2 schematically illustrates four examples of bit streams parsed by respective data unit parsers  12   a - 12   d . In the example shown, the unit parsers  12   a - 12   d  have first byte aligned the respective data streams  10   a - 10   d , and parsed the respective data streams into respective data units that are passed to the respective encoders  14   a - 14   d.    
     The successive data units are received by the encoders, which apply a respective one of the encoding schemes  14   a ,  14   b ,  14   c  and  14   d . Each encoding scheme performs a reversible encoding operation on each data unit independently. The four encoding schemes are subject to only one constraint. If the A1 byte (hexidecimal: F 6, binary 1111 0110) or the A2 byte (hexadecimal: 2 8, binary 0010 1000) is encoded by one of the encoding schemes, and subsequently decoded by any of the decoding schemes used to reverse any of the other encoding schemes, the result must not produce an A1 or an A2 byte. For the purposes of the present invention, the term “encoding scheme” is intended to encompass an identity mapping of data units. 
     The example illustrated in FIG. 2 shows how the four exemplary encoding schemes of the present embodiment modify example data units. The four exemplary encoding schemes (further illustrated in FIG. 4) are defined by the following four functions: 
     Encoding 1 (FIG. 4,  24 ): (abcdefgh)=(abcdefgh), 
     Encoding 2 (FIG. 4,  26 ): (abcdefgh)=(˜a˜b˜c˜d˜e˜g˜f˜h) 
     Encoding 3 (FIG. 4,  28 ): (abcdefgh)=(hgfedcba), and 
     Encoding 4 (FIG. 4,  30 ): (abcdefgh)=(˜h˜g˜f˜e˜d˜c˜b˜a), 
     where “˜” represents a boolean negation of a value of a bit. 
     The four encoding schemes are self-inverting, that is, applying any of the encoding schemes 1-4 to a data unit twice returns the original data unit. These four encoding schemes were selected because of the simplicity of implementation using simple logical circuits schematically illustrated in FIG.  4 . 
     The encoded bytes of each of the four data streams  10   a - 10   d  are then byte interleaved by the multiplexer  16  in a manner known in the art, to form the aggregate data stream  17 . 
     FIG. 3 is a schematic diagram that illustrates an example of the decoding and collating aspects of the embodiment of the invention shown in FIGS. 1 and 2. FIG. 3 illustrates the decoding process performed to recover the original data streams  10   a - 10   d . The aggregate data stream  17  is replicated to each of four deserializers  18   a - 18   d . The four deserializers  18   a - 18   d  are adapted to divide the aggregate data stream  17  into data words, which are further decoded, if required, into data units. As explained above, retrieving the four data streams involves applying to four replications  19   a - 19   d  of the aggregate data stream  17 , four respective decoding, frame detection and collating procedures. Each of the four frame detection and decoding procedures are associated with a one of the four data streams  19   a - 19   d , and uses decoders  20   a - 20   d  for reverting the encoding of the respective encoders  14   a - 14   c . The respective decoders  20   a - 20   d  revert only data units associated with the corresponding input data streams  10   a - 10   d , The decoded A1 and A2 framing bytes of the respective data streams  19   a - 19   d  can thus be detected. This permits respective data unit collators  22   a - 22   d  to locate the beginning of a frame, and to then select the respective data units that are a part of the frame, as described above. 
     As will be understood by persons skilled in the art, the A1/A2 framing bytes in the respective data streams  19   a - 19   d  are separated by m bytes (m=4, in this example). Consequently, the collators  20   a - 20   d  are programmed to detect the A1 byte and then inspect a subsequent M th  byte to determine if it is an A2 byte. If the m th  byte is an A2 byte, frame lock is declared. The collators  22   a - 22   d  then respectively select each m th  subsequent byte to reconstruct each of the respective data streams  10   a - 10   d  until an end of the frame is reached, at which time the process restarts with a detection of a next A1 byte, indicating the beginning of a new frame. Output of the collators  22   a - 22   d  is byte aligned. 
     FIG. 4 is a schematic diagram illustrating four exemplary encoding schemes in accordance with an embodiment of the invention. As shown in FIG. 4, a first encoding scheme  24  is a straight passthrough of a data unit. The encoding schemes  26  negates each bit of the data unit without changing an order of the respective bits in data unit. A third encoding scheme  28  reverses an order of the bits in the data unit, to produce a mirror image of the original data unit. With the encoding scheme  30 , the order of the bits in the data unit is reversed and each bit is negated. It should be noted that a second application of any one of these encoding schemes to a data unit returns the original data unit. The encoding schemes  24 - 30  can therefore be described as self-inverting, orthogonal encoding streams. 
     One application of the invention is to improve bandwidth usage in Wave Division Multiplexed (WDM) optical networks, while providing a service that remains transparent and protocol independent. The invention permits up to m data streams to be interleaved for transport without reformatting the frames or performing pointer processes. Thus, network operation is simplified, transport efficiency is improved and frames are delivered in a condition in which they were received. 
     The invention has been illustrated using a simple case in which m=4. As will be understood by those skilled in the art, however, m can be less than or greater than four, depending on the bandwidth of the input synchronous data streams and a capacity of the aggregate data path that carries the aggregate data stream  17 . It should also be understood that one or more data streams may be added to or dropped from the aggregate data stream without affecting the integrity of the data stream if the procedures described above are followed. 
     The embodiment of the invention described above is intended to be exemplary only. The scope of the invention is therefore intended to be limited solely by the scope of the appended claims.