Abstract:
An HDLC frame formation technique that calculates fields based on unscrambled data and combines unscrambled fields with scrambled data. Decoding HDLC frames includes determining integrity of the scrambled data based on the unscrambled fields.

Description:
DESCRIPTION OF THE ART  
       [0001]     Networks such as the Internet, Local Area Networks (LANs), and Wide Area Networks (WANs) typically transmit data between devices via frames of data. Networked devices may transmit data using Synchronous Optical Network/Synchronous Digital Hierarchy (SONET/SDH) or Packet Over SONET (POS) protocols. Internet Protocol (IP) packets can be encapsulated into Point-to-Point Protocol (PPP) frames that can be further encapsulated into High-level Data Link Control (HDLC) frames. HDLC frames can further be mapped into SONET/SDH frames. Encapsulation of data into HDLC frames and encapsulation of HDLC frames into SONET frames is specified by the Internet Engineering Task Force (IETF) in “PPP in HDLC-like Framing”, RFC 1662, published July 1994; “PPP over SONET/SDH”, RFC 2615, published June 1999; “IP Over SDH Using LAPS”, International Telecommunication Union (ITU)-T X.85, published March 2000; High-level Data Link Control (HDLC), International Organization for Standardization/International Electrotechnical Convention (ISO/IEC) 3309, published Jun. 1, 1991; as well as ITU-T X.86 Y.1323, Ethernet over LAPS, February 2001.  
         [0002]      FIG. 1  shows data-flow for HDLC byte-oriented processing in both transmit and receive directions. When mapping IP packets into a SONET/SDH payload according to IETF RFC 2615 and ITU-T LAPS X.85 (Packet-Over-SONET) or when mapping Ethernet frames into SONET/SDH payload (as per ITU-T LAPS X.86), data is scrambled after being processed for HDLC byte-oriented delineation. Scrambling prevents long sequences of zeroes that could cause loss of clock on the receiver side of an optical line. One drawback of HDLC byte-oriented frame delineation is the potential loss of bandwidth when the data to be delineated contains the same control characters that are used by the delineation mechanism (e.g.,  7 E and  7 D). Such characters in the data are stuffed ( 7 E is converted to  7 D- 5 E and  7 D is converted to  7 D- 5 D) in order to be distinguished from characters performing delineation functions that are not part of the data.  
         [0003]     In order to make uniform the impact of stuffing and prevent a malicious user from slowing down a link by sending packets full of control characters ( 7 E or  7 D), user data may be scrambled before byte stuffing. Scrambling user data before byte stuffing is called pre-HDLC scrambling. Scrambling user data before byte-stuffing can be applied before or after Frame Check Sequence (FCS) field insertion.  
         [0004]      FIG. 2  depicts a processing flow for a pre-HDLC scrambler on the transmission side to encode HDLC frames for transmission.  FIG. 2  also depicts a processing flow on the receive side to decode received HDLC frames. In this example, on the transmission side, the pre-HDLC scrambler receives a packet and scrambles the packet. In this example, Frame Check Sequence (FCS) calculations are made based on a scrambled payload. The FCS calculator and inserter calculates the FCS on the scrambled packet and combines the FCS with the scrambled packet. For example, byte stuffer replaces control characters, such as  7 D and  7 E (specified in POS), with a two byte sequence  7 D- 7 E or  7 D- 5 D. The flag inserter inserts one of more control characters (0× 7 E) to separate (delineate) HDLC frames.  
         [0005]     On the receive side, the frame delineator separates HDLC frames from one another. Byte de-stuffer transforms byte sequences back into control characters. FCS checker checks the validity of the FCS value prior to the packet being unscrambled by the descrambler. One drawback of the approach in  FIG. 2  is in the receive direction, an error in one packet may be propagated to a next packet. The descrambler will propagate an error from a first packet to a second packet and a check of the second packet&#39;s FCS will not detect the error in the second packet because the FCS is checked before descrambling. For example, referring to  FIG. 3 , if an error is present in a first received packet (packet  1 ), the error in the first received packet (packet  1 ) may be propagated to a second received packet (packet  2 ) and such error in packet  2  may go undetected.  
         [0006]      FIG. 4  depicts a processing flow for a pre-HDLC scrambler on the transmission side to encode HDLC frames as well as a processing flow on the receive side to decode HDLC frames. On the transmission side, FCS calculator and inserter calculates the FCS based on unscrambled user data and combines the FCS with the unscrambled user data. The scrambler scrambles the FCS value together with user data. In this example, byte stuffer and flag insertion perform similar actions as those described earlier. A drawback of this approach is that in the transmit direction, the expansion of data from byte-stuffing cannot be known before FCS has been calculated and a “back-pressure” mechanism is typically implemented to control a rate of data-flow to prevent overflow. This implementation also requires storage resources to accumulate bits between every stage.  
         [0007]     On the receive side, received user data and FCS may be unscrambled prior to the FCS portion being checked for validity. In this receive side processing, unlike in the example of  FIG. 2 , a transmission error propagated by the descrambler from a first received packet to the second received packet would be detected in the FCS check.  
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0008]      FIG. 1  shows data-flow in a HDLC byte-oriented frame delineation process in both transmit and receive directions.  
         [0009]      FIG. 2  depicts a processing flow for a pre-HDLC scrambler on the transmission side as well as a processing flow on the receive side to decode transmitted HDLC frames.  
         [0010]      FIG. 3  depicts an example of an error propagation.  
         [0011]      FIG. 4  depicts a processing flow for a pre-HDLC scrambler on the transmission side to encode HDLC frames as well as a processing flow on the receive side to decode HDLC frames.  
         [0012]      FIG. 5  depicts a suitable system embodiment in accordance with an embodiment of the present invention.  
         [0013]      FIG. 6A  depicts a flow diagram of one possible manner in which a line card processes packets and frames for transmission as SONET/SDH frames.  
         [0014]      FIG. 6B  depicts one possible manner in which a line card may process SONET/SDH frames received from a network.  
         [0015]      FIG. 7  depicts an HDLC encoder in accordance with an embodiment of the present invention.  
         [0016]      FIG. 8  depicts one possible implementation of a scrambler in accordance with an embodiment of the present invention.  
         [0017]      FIG. 9  depicts an example flow diagram of a process to encode HDLC frames in accordance with an embodiment of the present invention.  
         [0018]      FIG. 10  depicts an HDLC decoder in accordance with an embodiment of the present invention.  
         [0019]      FIG. 11  depicts one possible implementation of a descrambler in accordance with an embodiment of the present invention.  
         [0020]      FIG. 12  depicts an example flow diagram of a process to decode HDLC frames in accordance with an embodiment of the present invention. 
     
    
       [0021]     Note that use of the same reference numbers in different figures indicates the same or like elements.  
       DETAILED DESCRIPTION  
       [0022]      FIG. 5  depicts a suitable system embodiment in accordance with an embodiment of the present invention. System  500  may include line card  510 , line card  520 , switch fabric  530 , and backplane interface  540 . Line card  510  may be implemented as a SONET/SDH add-drop multiplexer, a Fibre Channel compatible line input, an Ethernet line input or a SONET/SDH line input.  
         [0023]     Line card  520  may be implemented as a transceiver capable of transmitting and receiving frames to and from a network that is compatible with SONET/SDH. For example, the network may be any network such as the Internet, an intranet, a local area network (LAN), storage area network (SAN), a wide area network (WAN). One implementation of line card  520  may include physical layer processor  522 , mapper  524 , and network processor  526 .  
         [0024]     Physical layer processor  522  may receive optical or electrical signals from the network and prepare the signals for processing by downstream elements such as mapper  524 . For example, physical layer processor  522  may convert optical signals to electrical format and/or remove jitter from signals from the network. For frames to be transmitted to the network, physical layer processor  522  may remove jitter from signals provided by upstream devices such as mapper  524  and prepare signals for transmission to the network, which may be optical or electrical format.  
         [0025]     To prepare frames for transmission to a network, mapper  524  may construct HDLC frames at least from IP packets and/or Ethernet frames. Mapper  524  may utilize embodiments of the present invention to build HDLC frames. Further, mapper  524  may construct SONET/SDH frames from HDLC frames and overhead.  
         [0026]     For SONET/SDH packets received from a network, mapper  524  may decode HDLC frames to extract IP packets and Ethernet frames (as well as other user data and other information). To decode HDLC frames, mapper  524  may use embodiments of the present invention. Mapper  524  may transfer IP packets and Ethernet frames (as well as other user data) to a higher layer level processor such as a network processor  526 . For example, mapper  524  and network processor  526  may intercommunicate using an interface compatible for example with SPI-4.  
         [0027]     Network processor  526  may perform layer  2  or layer  3  (as well as other higher layer level) processing on IP packets and Ethernet frames (as well as other user data and other information) provided by and to mapper  524  in conformance with applicable link, network, transport and application protocols. Network processor  526  also may perform traffic management at the IP layer.  
         [0028]     In one implementation, components of line card  520  may be implemented among the same integrated circuit. In another implementation, components of line card  520  may be implemented among several integrated circuits that intercommunicate using, for example, a bus or conductive leads of a printed circuit board.  
         [0029]     Backplane interface  540  may be implemented as a single or multi-pin interface and may be used by line cards to interface with switch fabric  530 . Switch fabric  530  may transfer IP packets or Ethernet packets (as well as other information) between line cards based on relevant address and header information.  
         [0030]      FIG. 6A  depicts a flow diagram of one possible manner in which line card  520  processes packets and frames (as well as other user data and other information) for transmission as SONET/SDH frames. Action  610  of  FIG. 6A  may include performing layer  2  and layer  3  processing on IP packets and Ethernet frames in conformance with layer  2  and layer  3  protocols. Action  620  may include performing HDLC encoding and framing of IP packets and Ethernet frames (or other types of user data and information) in conformance with HDLC standards. Action  620  may utilize embodiments of the present invention. Action  630  may include performing SONET/SDH frame encapsulation of HDLC frames in preparation to transmit such SONET/SDH frames. Action  640  may include performing physical layer processing on the SONET/SDH frames. Action  645  may include transmitting SONET/SDH frames to a network medium such as a fiber optic cable or other medium.  
         [0031]      FIG. 6B  depicts one possible manner in which line card  520  may process SONET/SDH frames received from a network. Action  650  of  FIG. 6B  may include receiving a SONET/SDH frame from a network medium and performing physical layer processing on the received SONET/SDH frame. Action  660  may include extracting HDLC frames from the SONET/SDH frame. Action  670  may include HDLC decoding and extracting IP packets and Ethernet frames (as well as other types of user data and information) from HDLC frames. Action  670  may utilize embodiments of the present invention. Action  680  may include performing higher layer processing (e.g., layer  2  and layer  3 ) on IP packets and Ethernet frames (as well as other types of user data and information) in conformance with layer  2  and layer  3  protocols. Action  680  may further include traffic management of received IP packets and Ethernet frames (and other types of user data).  
         [0032]      FIG. 7  depicts an HDLC encoder  700  in accordance with an embodiment of the present invention, although other implementations may be used. One implementation of HDLC encoder  700  may include field calculator  710 , scrambler  715 , field inserter  720 , byte stuffer  730 , and flag inserter  740 . HDLC encoder  700  may receive IP packets and Ethernet frames (as well as other information such as PPP, Fibre Channel or Resilient Packet Ring packets) from a user data source such as, but not limited to, a system interface that intercommunicates with an upper-layer processing device such as a network processor. HDLC encoder  700  may build HDLC frames using IP packets and Ethernet frames (as well as other information such as PPP, Fibre Channel or Resilient Packet Ring packets). HDLC frames may be used to build SONET/SDH frames. In one implementation, IP packets may be encapsulated into PPP frames first and then encapsulated into HDLC frames.  
         [0033]     Field calculator  710  may calculate fields based on the received IP packets and Ethernet frames (as well as other information such as PPP, Fibre Channel or Resilient Packet Ring packets). For example, field calculator  710  may determine the FCS field as well as an HDLC frame header in conformance with HDLC standards. Under POS, the FCS field may be 16 or 32 bits, however other number of bits may be used. Field calculator  710  may use a linear feedback shift register (LFSR) or a look-up-table to determine the FCS value based on intended contents of an HDLC frame.  
         [0034]     Scrambler  715  may scramble the IP packets and Ethernet frames as well as other user data contents of an HDLC frame except for any FCS field or other specified field(s). Scrambler  715  may perform scrambling in conformance with ITU-T LAPS X.85 (Packet-Over-SONET) and relevant IETF RFCs.  FIG. 8  depicts one possible implementation of a scrambler although other implementations may be used. The scrambler may include a shift register and an XOR logical device. Each bit of a scrambled signal provided by the scrambler may be a result of an XOR operation between a bit from the shift register and a bit from the unscrambled input. For example, the shift register may be implemented a 43 bit serial shift register, although other numbers of bits may be used. For the first packet, the shift register may be initialized to all zeros. The contents of the shift register at the beginning of the scrambling operation for the second packet is the contents of the scrambler after scrambling the first packet.  
         [0035]     One advantage, although not a necessary feature or aspect, of one embodiment of the present invention, is that providing scrambling before byte stuffing may reduce the likelihood of byte stuffing in byte stuffer  730  and thereby may reduce the likely size of a stuffed HDLC frame.  
         [0036]     One advantage, although not a necessary feature or aspect, of one embodiment of the present invention is that the number of bytes stuffed for each HDLC frame may be predicted after scrambler  715  scrambles user data. For example, scrambler  715  may provide each user data byte to a byte-stuffing predictor  717  that counts  7 D and  7 E characters (or other characters that are to be replaced with stuff characters) and can thereby predict the number of bytes that will be added by byte stuffer  730 . In one implementation, the number of bytes that will be stuffed can be predicted before FCS field calculation, although other implementations may differ. The byte-stuffing predictor  717  can signal back to a source of traffic to HDLC encoder  700  to slow down or speed up user data traffic. Accordingly, one advantage, but not a necessary feature, of an embodiment of the present invention is a likelihood of overflow (i.e., more bytes generated during the data path of HDLC encoder  700  than the data path can handle) may be reduced. One advantage, but not a necessary feature, of an embodiment of the present invention is that to the extent memory/overflow devices (not depicted) are provided between stages of HDLC encoder  700  to accommodate overflow, less memory storage capability may be used.  
         [0037]     Field inserter  720  may add the unscrambled field(s) determined by field calculator  710  to the scrambled user data portion from scrambler  715 . For example, one possible location to add an unscrambled header is at the beginning of an HDLC frame. For example, one possible location to add an unscrambled FCS field is to the end of an HDLC frame.  
         [0038]     Byte stuffer  730  may perform byte stuffing in conformance with HDLC standards. For example, byte stuffer  730  may replace control characters (such as  7 D and  7 E) with two-byte sequences (such as  7 D- 7 E and  7 D- 5 D, respectively). Other control characters may be modified or replaced with other characters.  
         [0039]     Flag inserter  740  may insert one of more control characters (e.g., 0× 7 E) to delineate each HDLC frame in conformance with HDLC standards (in particular, byte-oriented HDLC). Thereafter, a mapper may map HDLC frames into payload of a SONET/SDH frame(s).  
         [0040]      FIG. 9  depicts an example flow diagram of a process to encode HDLC frames in accordance with an embodiment of the present invention. Action  905  may include receiving an IP packet or Ethernet frame (as well as other information such as PPP, Fibre Channel or Resilient Packet Ring packets).  
         [0041]     Action  910  may include calculating one or more fields based on the packet or frame received in action  905 . For example, one field may be an FCS field. Another field may be an HDLC frame header.  
         [0042]     Action  915  may include scrambling the packet(s), frame(s), and other information received in action  905  in conformance with ITU-T LAPS X.85 (Packet-Over-SONET) and relevant IETF RFCs.  
         [0043]     Action  920  may include predicting byte stuffing for the current HDLC frame.  
         [0044]     Action  925  may include combining the unscrambled fields determined in action  910  with the scrambled packet(s), frame(s), and other information from action  915 .  
         [0045]     Action  930  may include performing byte stuffing in each HDLC frame in conformance with the HDLC standards. For example, byte stuffing may replace control characters (such  7 D and  7 E) with other sequences (such as  7 D- 7 E and  7 D- 5 D, respectively). Action  935  may include inserting control characters to separate HDLC frames in conformance with HDLC.  
         [0046]      FIG. 10  depicts an HDLC decoder  1000  in accordance with an embodiment of the present invention, although other implementations may be used. HDLC decoder  1000  may be used to extract user data (such as IP packets and Ethernet frames as well as other information such as PPP, Fibre Channel or Resilient Packet Ring packets) from HDLC frames. For example, HDLC frames may be transmitted in a SONET/SDH frame and provided by a mapper to the HDLC decoder  1000 . One implementation of HDLC decoder  1000  may include frame delineator  1010 , byte de-stuffer  1015 , field extractor  1020 , de-scrambler  1025 , and field checker  1030 .  
         [0047]     Frame delineator  1010  may remove control characters (e.g., 0× 7 E) that separate HDLC frames from one another and provide each HDLC frame for further processing. Byte de-stuffer  1015  may transform replacement sequences, such as  7 D- 7 E and  7 D- 5 D, into control characters, such  7 D and  7 E.  
         [0048]     Field extractor  1020  may remove unscrambled fields (such as the FCS field and other fields such as an HDLC frame header) from the HDLC frame.  
         [0049]     De-scrambler  1025  may apply de-scrambling to the scrambled HDLC frame in conformance with ITU-T LAPS X.85 (Packet-Over-SONET) and relevant IETF RFCs except for the FCS field (and other fields) extracted by the field extractor  1020 .  FIG. 11  depicts one possible implementation of a descrambler although other implementations may be used. The descrambler may include a shift register and an XOR logical device. Each bit of a descrambled signal provided by the descrambler may be a result of an XOR operation between a bit from the shift register and a bit from the scrambled input. For example, the shift register may be implemented as a 43 bit serial shift register, although other numbers of bits may be used. For the first packet, the shift register may be initialized to all zeros. The contents of the shift register at the beginning of the descrambling operation for the second packet is the contents of the descrambler after descrambling the first packet.  
         [0050]     Field checker  1030  may check whether the unscrambled field (e.g., FCS and/or HDLC frame header) is correct in conformance with HDLC standards. For example, field checker  1030  may determine an FCS value based on the descrambled HDLC frame and compare the FCS value against the extracted unscrambled FCS field. A transmission error propagated by the descrambler  1025  from one packet to a sequential packet may be avoided because of detection in the FCS check.  
         [0051]      FIG. 12  depicts an example flow diagram of a process to decode HDLC frames in accordance with an embodiment of the present invention. The process of  FIG. 12  may receive HDLC frames provided from the payload of a SONET/SDH frame. Action  1205  may include removing HDLC frame delineation characters from HDLC frames. For example, HDLC frame delineation characters (e.g., 0× 7 E) may define the boundaries of an HDLC frame.  
         [0052]     Action  1210  may include transforming stuffed sequences, such as  7 D- 7 E and  7 D- 5 D, into control characters, such as  7 D and  7 E. Action  1215  may include removing unscrambled fields (such as the FCS field and other fields such as an HDLC frame header) from the HDLC frame.  
         [0053]     Action  1220  may include apply de-scrambling to the scrambled HDLC frame in conformance with ITU-T LAPS X.85 (Packet-Over-SONET) and relevant IETF RFCs except for the FCS field (and other fields) extracted in action  1215 .  
         [0054]     Action  1225  may include determining whether the unscrambled FCS field is correct in conformance with IETF and ITU-T standards. For example, action  1225  may determine an FCS value based on the descrambled HDLC frame and compare the determined FCS value against the extracted unscrambled FCS field. The integrity of the HDLC frame can be determined based on whether the determined FCS value matches the extracted unscrambled FCS field.  
         [0055]     The drawings and the forgoing description gave examples of the present invention. While a demarcation between operations of elements in examples herein is provided, operations of one element may be performed by one or more other elements. The scope of the present invention, however, is by no means limited by these specific examples. Numerous variations, whether explicitly given in the specification or not, such as differences in structure, dimension, and use of material, are possible. The scope of the invention is at least as broad as given by the following claims.