Classifications

• • H—ELECTRICITY
  • H04—ELECTRIC COMMUNICATION TECHNIQUE
  • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
  • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
  • H04L9/40—Network security protocols
• • H—ELECTRICITY
  • H04—ELECTRIC COMMUNICATION TECHNIQUE
  • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
  • H04L69/00—Network arrangements, protocols or services independent of the application payload and not provided for in the other groups of this subclass
  • H04L69/22—Parsing or analysis of headers

Definitions

• the present invention relates to data communication switching and, more particularly, to data communication switching hardware for assembling packets for transmission on an output
• Data communication switches have switching engines which receive inbound packets on inputs and switch them as outbound packets on outputs.
• the inbound packets generally have an inbound header including media access control (MAC) addresses
• the inbound header is stripped from the packet and the addresses or identifiers contained therein are resolved to an outbound header suitable for interpretation at the packet's "next hop" through the network.
• the outbound header is appended to the stripped packet to form an "encapsulated" outbound packet
• the outbound header and the stripped packet are often separately-sourced into a packet assembly in a series of "bursts" of K-bit wide data, where K is greater than one.
• Such "chunky" packet transfer presents some technical obstacles to "on the fly” encapsulation. For one, jf the inbound header ended on a whole width (i.e., both half-widths of the final burst containing data for the inbound header included valid header data) but the corresponding outbound header ends on a half-width
• the start of the stripped packet will, if not advanced (or delayed) appropriately, trail (or lead) the outbound header by a half-width.
• the stripped packet will, if not advanced (or delayed) appropriately, trail (or lead) the outbound header by either a half- width or a whole width. If this misalignment created by "chunky" transfer from multiple sources is not corrected, packets will be encapsulated improperly and spurious data or system errors may result.
• the present invention provides an "on the fly" packet assembly for a data communication switching engine which assembles packet elements separately-sourced in multi-bit bursts while correcting any misalignment created by "chunky" transfer.
• a data communication switching engine which assembles packet elements separately-sourced in multi-bit bursts while correcting any misalignment created by "chunky" transfer.
• the stripped packet is realigned by a half-width to align the last half-width of the outbound header and the first half-width of the stripped packet.
• serially-implemented alignment and merger operations format the outbound header and stripped packet into an encapsulated packet which may be transferred contiguously on an output.
• the alignment unit may be arranged as a selectively implemented half-width register followed by one or more full-width registers.
• the half-width register captures half-widths of the stripped packet while the other half-widths are allowed to flow directly into a full-width register, This activity creates an offset in the stripped packet which matches that of the outbound header (i.e., afterward the outbound header ends and the stripped packet begins on a half-width).
• the half-width register captures half-widths of the stripped packet while the other half-widths are allowed to flow directly into a full-width register. This activity creates an offset in the stripped packet which matches that of the outbound header (i.e., afterward the outbound header ends and the stripped begins on a whole burst).
• the half-width register is bypassed and whole widths of the stripped packet are allowed to flow directly into a full-width register.
• the merger multiplexor may be arranged as a two-width to one-width multiplexor which from a given two-width input may select as an output either a whole width from the outbound header, a whole width from the stripped packet, or a half-width from each. More particularly, when the outbound header ends on a whole width, the merger multiplexor always selects whole widths from the outbound header until the entire header has been transferred and then selects whole bursts from the stripped packet until the entire stripped packet has been transferred. When the outbound header ends Ion a half- width, the same selection sequence is followed except when the last half-w- ⁇ h of the outbound header and the first half-width of the stripped packet are made available as inputs.
• the merger multiplexor selects the last half-width of the outbound header and the first half-width of the stripped packet to "merge" the output header with the stripped packet. Because of the previous alignment function jperforraed selectively by the alignment unit, half-widths may always be clocked to arrive at the merger multiplexor in the manner required for the merger multiplexor to combine the outbound header and the stripped packet into an encapsulated packet adapted for contiguous transfer.
• an update unit may be interposed to selectively update half-width, full-width or multiple width fields in the packet.
• Figure 1 is a block diagram of a data communication switching engine
• Figure 2 is a more detailed block diagram of the packet assembly element of the switching engine of Figure 1;
• Figures 3A through 3D illustrate the different inbound header/outbound header combinations which the packet assembly element of Figure 2 is arranged advantageously to treat differently to form encapsulated packets;
• FIG. 4 is a more detailed block diagram of the alignment unit of the switching engine of Figure 1;
• FIG. 5 is a more detailed block diagram of the update unit of the switching engine of Figure 1;
• Figure 6 is a more detailed block diagram of the merger multiplexor of the switching engine of Figure 1 and its associated logic;
• Figure 7A illustrates the serial operation of the alignment unit and the merger multiplexor in the situation where the inbound header and outbound header do not have a half-width divergence and the outbound header ends on a whole width;
• Figure 7B illustrates the serial operation of the alignment unit and the merger multiplexor in the situation where the inbound header and outbound header do not have a half-width divergence and the outbound header ends on a half-width;
• Figure 7C illustrates the serial operation of the alignment unit and the merger multiplexor in the situation where the inbound header and outbound header have a half- width divergence and the outbound header ends on a half-width
• Figure 7D illustrates the serial operation of the alignment unit and the merger multiplexor in the situation where the inbound header and outbound header have a half- width divergence and the outbound header ends on a whole width.
• FIG. 1 a switching engine 100 in which the present invention may be implemented is shown.
• Inbound packets arrive in receive FIFO 110.
• Identifiers in the headers of inbound packets are transmitted to switching logic 120 for a switching decision. If the switching decision indicates forwarding, switching logic 120 transmits a forwarding index to header table 140 to retrieve an appropriate outbound header.
• Identifiers transmitted to switching logic 120 may include Open System Interconnection (OSI) Layer Two (Bridging) Layer Three (Network) and Layer Four (Transport) addresses and identifiers, by way of example.
• Switching logic 120 may make the switching decision by performing associative comparisons of such identifiers with known identifiers stored in a memory within switching logic 120.
• Such a memory may be a content-addressable memory (CAM) or may be a random access memory (RAM).
• CAM content-addressable memory
• RAM random access memory
• Packet assembly 150 receives bursts of data separately from header
• FIFO 145 and from packet FIFO 130 and combines such data "on the fly" into encapsulated packets which may be transferred in a contiguous manner on transmit FIFO
• Header and packet data are transferred in K-bit wide bursts, where K is greater than one. All, half or none of the bits in each burst may be valid. When all bits are valid, a burst transfers a whole width of data. When half of the bits are valid, the burst transfers a half-width of data. Thus, by way of example, where K is sixteen, each burst may transfer two valid bytes (a whole width), one valid byte (a half-width) or no valid bytes. Of course, the value of K may differ in other embodiments without departing from the inventive scope.
• Alignment unit 210 receives stripped packet data in bursts from packet FIFO 130, performs necessary realignments, and forwards the data to update unit 220.
• Stripped packet data includes inbound packet contents, excluding the stripped inbound header.
• Update unit 220 separately receives outbound header data in bursts from header FIFO 145, Update unit 220 makes necessary updates to received data and forwards the data in bursts to merger multiplexor 230.
• Merger multiplexor 230 merges outbound header data and stripped packet data into an encapsulated packet suitable for contiguous transmission on transmit FIFO 160, and delivers the encapsulated packet in bursts to assembly register 240. Updates and merger are assisted by multiplexor control 250.
• Multiplexor control 250 instructs the multiplexors in update unit 220 and merger multiplexor 230 to select appropriate half-widths from among the currently available widths of data to achieve the desired updates (in the case of update unit 220) and to form the encapsulated packet (in the case of merger multiplexor 230).
• a significant advantage of the present invention is "on the fly" selective alignment and merger of separately-sourced outbound header and stripped packet data to form encapsulated packets.
• FIGs 3A through 3D The scenarios requiring the application of different alignment and merger rules are shown in Figures 3A through 3D.
• inbound header 310 and outbound header 311 both end on a whole width.
• stripped packet 312 and outbound header 311 both begin on a whole width and may be combined into encapsulated packet 313 without alignment or merger.
• inbound header 320 and outbound header 321 both end in a half-width. Therefore, stripped packet 322 and outbound header 321 both begin on a half-width and may be combined into encapsulated packet 323 without alignment, but require merger in order to form encapsulated packet 323.
• inbound header 330 ends in a whole width while outbound header 331 ends in a half-width. Therefore, stripped packet 332 and outbound header 331 require both alignment and merger in order to form encapsulated packet 333.
• inbound header 340 ends in a half-width while outbound header 341 ends in a whole width. Therefore, stripped packet 342 and outbound header 341 require alignment, but do not require merger, in order to form encapsulated packet 343.
• Unit 210 includes half-width register 410 followed by full-width registers 420, 430.
• the stripped packet arrives at unit 210 from packet FIFO 130 in a series of bursts, which are operatively treated as half-burst pairs.
• bypass logic 440 directs the half- widths in the half-burst pairs on one of three paths, depending on (i) whether or not there is a half-width divergence between the inbound header and the outbound header and (ii) whether, if there is a half-width divergence, the outbound header ends on a half- width or a whole width.
• bypass logic 440 makes these two determinations by consulting the least significant bit of an offset field in the stripped packet (which indicates whether the start of the stripped packet was offset from the start of the inbound header by a half-width and, therefore, whether the stripped packet begins on a half-width or a whole width) and the least significant bit in a header length field in the outbound header (which indicates whether the outbound header ends on a half-width or a whole width).
• Update unit 220 is shown in greater detail. Update unit
• the 220 receives the stripped packet from alignment unit 210 in a series of bursts, which are operatively treated as half-burst pairs, and receives the outbound header from header FIFO 145 in a series of whole bursts.
• the half-widths of the stripped packet are inputs to half-width multiplexors 520, while the whole widths of the outbound header are inputs to whole width multiplexor 530.
• Multiplexors 520, 530 also have as inputs data from various ones of update registers 510.
• multiplexor control 250 instructs each of multiplexors 520, 530 to select one of the inputs as an output, depending on the result of a comparison of update flags with the current burst count
• multiplexor control 250 has update flags sufficient to indicate for each of update registers 510 the burst cycles on which the multiplexors are to select as outputs the inputs from the various update registers.
• a burst counter associated with multiplexor control 250 is incremented on each burst cycle and the current counter value is compared for a match with the update flags.
• multiplexor control 250 instructs the appropriate one or both of multiplexors 520, 530 to select the input from the update register corresponding to the rnatching update flag.
• multiplexors 520, 530 select the input from alignment unit 210 and/or header FIFO 145, respectively.
• packet fields which require modification on a packet-by-packet basis can be updated. Fields requiring packet-specific modification may include, by way of example, those which indica.e the length of a packet or the length of a packet header and/or those which indicate the number of "hops" a packet has traversed or its remaining time-to-live.
• update unit 220 is shown to precede merger multiplexor 230 in series, it may be interposed after merger multiplexor 230 in other embodiments.
• merger multiplexor 230 receives as inputs the stripped packet and outbound header (as modified by update unit 220).
• the stripped packet arrives in a series of half-burst pairs and the outbound header arrives in a series of whole bursts which may be operatively treated as half-burst pairs by multiplexor 230.
• multiplexor control 250 instructs merger multiplexor 230 to select as outputs two of the upon to four half-width inputs, depending on the application of a selection matrix to the current burst count.
• multiplexor control 250 has access to merger information sufficient to indicate (i) the total length (in half-widths) of the outbound header; (ii) whether or not there was a half-width divergence between the inbound header and the outbound header; and (iii) whether the outbound header ends on a whole width or a half-width. From the foregoing information, a complete selection matrix for the encapsulated packet is resolved, The burst counter associated with multiplexor control 250 is incremented on each burst cycle and the selection matrix is applied to the current counter value to obtain a selection instruction.
• the selection instructions are used to control merger multiplexor 230 to select as outputs on the current burst cycle the two half-width inputs which are required in order to successfully merge the separately-sourced outbound header and stripped packet (as modified by update unit 220) into an encapsulated packet arranged for contiguous transmission.
• the selected whole widtl outputs are delivered to assembly register 240 for temporary storage en route to transmit FIFO 160.
• Figures 7A through 7D the selective alignment and merger operation of the present invention is shown for the four possible inbound/outbound header combinations. It is assumed for clarity in Figures 7A through 7D that no half-widths (e.g., A, B, C, D) are displaced in update unit by substitute half-widths (e.g., A', B', C, D') and that the arrival of half-widths at assembly registers is delayed by a fixed number of burst cycles U.
• Figure 7A illustrates the scenario wherein the inbound header and outbound header do not have a half-width divergence and the outbound header ends on a whole width.
• the stripped packet is arranged in packet FIFO 701 A to begin on a whole width A/B while the outbound header is arranged in header FIFO 711 A to end on a whole width Y/Z.
• burst cycle N initial whole width A/B is stored in packet FIFO 701 A as shown. Because there is no half-width divergence, realignment of the stripped packet is not required. Therefore, on burst cycle N+l, whole width A B bypasses half- width register 702A and flows into full-width register 703A.
• terminal whole width Y/Z of the outbound header is aligned for arrival from header FIFO 711 A as shown.
• initial whole width A B of the stripped packet advances to full-width register 704A.
• terminal whole width Y/Z of the outbound header is selected by merger multiplexor 721 A and delivered into assembly register.
• initial whole width A/B of the stripped packet is selected by merger multiplexor 721A and delivered into assembly register 722A.
• Figure 7B illustrates the scenario wherein he inbound header and outbound header do not have a half-width divergence but the outbound header ends on a half-width.
• the stripped packet is arranged in packet FIFO 701B to begin on a half- width A while the outbound header ends on a half-width Z.
• burst cycle N initial half- width A and whole width B/C which immediately follows are queued in packet FIFO 701B as shown. Because there is no half-width divergence, realignment of the stripped packet is not required. Therefore, on burst cycle N+l, half-width A bypasses half-width register 702B and flows into full-width register 703B.
• balf-width A advances to full-width register 704B while whole width B/C bypasses half-width register 702B and flows into full-width register 703B.
• terminal half-width Z of the outbound header is aligned for arrival from header FIFO 71 IB as shown.
• whole width B/C of the stripped packet advances to full- width register 704B.
• terminal half-width Z of the outbound header and initial half-width A of the stripped packet are selected by merger multiplexor 721B and delivered into assembly register 722B.
• half-width B is stored in half-width register 702C while half-width A flows into full-width register 703C.
• half- width A advances to full-width register 704C while realigned whole width B/C flows into full-width register 703B.
• terminal half-width Z of the outbound header is aligned for arrival from header FIFO 711C as shown.
• burst cycle N+3 whole width B/C of the stripped packet advances to full-width register 704C
• terminal half-width Z of the outbound header and initial half-width A of the packet base are selected by merger multiplexor 721 C and delivered into assembly register 722C.
• whole width B/C of the stripped packet is selected by merger multiplexor 721 C and delivered into assembly register 722C.
• Figure 7D illustrates the scenario wherein the inbound header and outbound header have a half-width divergence and the outbound header ends on a whole width.
• the stripped packet is arranged in packet FIFO 70 ID to begin on a half-width A while the outbound header ends on a whole width Y/Z.
• initial half-widlh and whole width B/C which immediately follows are queued in packet FIFO 701 C as shown. Because there is a half-width divergence and the outbound header ends on a whole width, a half-width to whole width realignment of the stripped packet is required.
• half-width A is stored in half-width register 702D, Separately, on burst cycle N+l, terrriinal whole width Y/Z of the outbound header is aligned for arrival from header FIFO 71 ID as shown.
• realigned whole width A/B advances to full-width register 704D and half-width C flows into half- width register 702D.
• terminal whole width Y/Z of the outbound header and is selected by merger multiplexor 721D ind delivered into assembly register 722D.
• whole width A/B of the packet base is selected by merger multiplexor 721D and delivered into assembly register 722D.

Landscapes

• Engineering & Computer Science (AREA)
• Computer Security & Cryptography (AREA)
• Computer Networks & Wireless Communication (AREA)
• Signal Processing (AREA)
• Data Exchanges In Wide-Area Networks (AREA)

Applications Claiming Priority (3)

Publications (1)

Family

ID=22265668

Family Applications (1)

Country Status (4)

Families Citing this family (5)

Family Cites Families (1)

• 1999
  • 1999-06-15 EP EP99928014A patent/EP1004187A1/de not_active Withdrawn
  • 1999-06-15 JP JP2000555396A patent/JP2002518938A/ja active Pending
  • 1999-06-15 CN CN99800960.1A patent/CN1272993A/zh active Pending
  • 1999-06-15 WO PCT/EP1999/004377 patent/WO1999066678A1/en not_active Ceased

Non-Patent Citations (1)

Also Published As

Similar Documents

Legal Events