Note: Descriptions are shown in the official language in which they were submitted.
WO 94/22253 ~15 ~ 013 PCT/EP93/00677
DESCRIPTION
Method and Apparatus for Extractin~ Connection Information
sfrom Protocol Headers
TECHNICAL FIELD
10 The present invention concerns a method and an apparatus for scanning data
streams in a communication network and extracting connection information to
provide for unique protocol connection identifiers.
BACKGROUND OF THE INVENTION
The technological convergence of computer and communication networks, as
well as the fast development in either one of these two areas, has led to such
an intimate mixture of information processing and communication that the
transmission and exchange of data, voice, images etc. becomes more and
20 more complex. Each transmission or exchange of information - information
used as synonym for various kinds of data, services, and communications -
has necessarily to be governed by rules of procedure.
When different units, e.g. two remote computer terminals, or two procedures
25 are interacting via an interface, which not necessarily has to be a hardware
interface, respective protocols are employed. Depending on the network,
various protocol~ are hierarchic~slly ordered, resulting in a vertical stack of
protocols, each of these protocols interacting with the adjacent ones. Basic
transport protocols are known to organize the information exchange and
30 transmission bet~veen remote systems, such as host computers. A typical
example is the ARPA (Advanced Research Projects Agency) host-to-host
protocol. Such a basic protocol enables the higher-level protocols of the
WO 94/222S3 21~ 8 01~ PCT/EP93/00677
vertical protocoi stack to base all their operations on the basic protocol
mechanisms .
Depending on the network environment, there are several higher-level
5 protocols set up on the basic protocol. A schematic representation of a typical
vertical protocol stack, known as OSI (Open Systems Interconnection)
reference model for CCITT (Consultative Committee on International
Telephone and Telegraph) applications is defined in the CCITT
Recommendation X.200, "Reference Model of Open Systems Interconnection
for CCITT Applications", Blue Book, Fascicle V111.4, Geneva, 1989. Said OSI
reference model uses seven levels, referred to as layers. Each layer has its
own specific function and offers a defined service to the layer above using the
services provided by the layer below.
15 If an application program, for example, which runs on a first system requiresthe use of data held in a second, remote system, an exchange of information
takes place. When said second system receives a request to send a specific
data packet, this data packet has to be transmitted from the highest protocol
level, e.g. the application layer, down through all lower protocol levels, prior20 to be sent along the physical link. Each of these protocol layers adds its
layer-specific connection information to the data packet received from the
higher layer. Therefore, a communication connection between two systems is
defined in a packet header, hereinafter referred to as protocol header, by the
aggregate of fields carrying connection information of the vertical protocol
25 stack.
When receiving a data stream made up of data packets at a receiver site, prior
to routing, multiplexing or compressing it. said protocol header has to be
scanned to extract the respective words comprising connection information for
30 further processing
To date, most of the protocol connections are identified by sequentially
processing the protocol headers in software. This operation consumes a
~ 8~
WO 94122253 PCT/EP93/00677
considerable amount of time in the protocol processing, in particular when
dealing with many connections, e.g. in a server, or when processing
multimedia data streams.
5 A microprogrammed controller, used to recognize the protocol type of a
protocol header and to extract protocol specific data fields, has been
described in "Implementing PE-1000 Based Internetworking Nodes", H.W. Chin
et al., Part 3 of 3, Transfer, Vol. 5, No. 3, May/June 1992,pp. 5 - 8.
10 The hardware implementation of a routing table for the translation of packet
identifiers into an appropriate physical output link is described in "Putting
Routing Tables Ir Silicon", T.-B. Pei and C. Zukowski, IEEE Network Magazine,
January 1992, pp. 42 - 50. This approach is mainly characterized in that a
Content-Addressable Memory (CAM) is employed to match connection
15 information in the header of a single protocol. In addition, the advantages and
disadvantages of CAMs versus conventional Random-Access-Memories
(RAM), used to store routing information, have been evaluated by Pei and
Zukowski .
20 Neither any of the two systems above, both of them relating to the solution of
sub-problems, nor the known software approaches allow fast processing of
multiple transport protocols such as TCP (Transmission Control Protocol) -
"Transmission Control Protocol; DARPA Internet Program Protocol
Specification", RFC 793, DARPA, September 1981 - and XTP (Express
Transport Protocol) -"XTP Protocol Definition", Protocol Engines Incorporated,
Revision 3.6., edited by Protocol Engines, Mountain View, CA, 11 January 1992
- which build on the Internet Protocol (IP) - "Internet Protocol; DARPA InternetProgram Protocol Specification", RFC 791, DARPA (Defense Advanced
Research Projects Agency), September 1981 - or TP4 (Transport Protocol,
30 Type 4) - "Connection Oriented Transport Protocol Specification", ISO/IEC
JTC1 Draft International Standard ISO/IEC DIS 8073 - which builds on CLNP
(Connectionless Network Protocol) - "Protocol for Providing the
Connectionless-Mode Network Service", ISO ISO/IEC 8473. The abbreviation
WO 94/22253 PCTIEP93/00677
2l58~l3
RFC, as herein used, is an acronym of the term Request for Comments. In
addition, the present invention is well suited for processing multimedia trafficas for example ST-II (Stream protocol, version 2) - "Experimental Internet
Stream Protocol; Version 2 (ST-II)", RFC 11~0, October 1990, edited by C.
5 Topolcic. The processing of protocol headers and the recognition of different
protocol types in real time is a very complicated and difficult undertaking. In
almost all netwcrk systems, header processing is still a major CPU-cycle
(Central Processor Unit) consuming activity. The claimed invention does not
only extract protocol data fields, see H.W. Chin et al., but uses these fields to
10 extract a unique connection identifier. This operation is performed in
real-time. Additionally, the present method and apparatus are designed for
processing protocol stacks.
It is an object of the present invention to provide a method for improved
15 header processing in networks carrying traffic of various protocols.
It is a further object of the present invention to provide a method for fast andreliable processing of addressing, i.e. connection, information of multiprotocoldata streams.
It is another ob,ect of the present invention to provide a method for fast and
reliable processing of multiprotocol data streams comprising multimedia data.
It is an object of the present invention to provide a method which allows
25 real-time processing of addressing, i.e. connection, information of complex
protocol headers.
It is another object of the present invention to provide a hardware
implementation of said methods.
WO 94/22253 21~ ~ 0 13 PCT/EP93/00677
SUMMARY OF THE INVENTION
.
The above objects have been accomplished by providing a method in
accordance with claim 9 and a hardware implementation, referred to as
5 Protocol Filter, of said method in accordance with claim 1. This method and
apparatus are characterized in that the protocol-type information of a first
protocol is extracted and the protocol information of protocols built on said
first protocol are read, sequentially. The protocol-type information and said
protocol information are applied to the input of a CAM to provide an address
at the CAM's output each time the information applied to this input matches
information stored in said CAM. The addresses provided at the output are
concatenated to a unique connection identifier.
DESCRIPTION OF THE DRAWINGS
The invention is described in detail below with reference to the following
drawings:
FIG. 1 shows a schematic block diagram of the Protocol Filter in
accordance with the first embodiment of the present invention.
FIG. 2 shows a data stream preceded by a protocol header comprising
header fields of two different protocols.
25 FIG. 3 shows a LLC (Logical Link Control) frame.
FIG. 4 shows the hierarchical structure of the TCP (Transmission Control
Protocol) which buTlds on IP (Internet Protocol), and the ST-II
protocol derived from the IP.
FIG. 5 shows the hierarchical structure of the TP4 (Transport Protocol,
Type 4) which builds on CLNP (ConnectionLess Network
Protocol).
wO 94/22253 PCTIEP93/00677
2~8Q~ 6
FIG. 6A shows the fieids of a TCP header which builds on an IP header.
FiG. 6B shows the fields of a ST-II header.
FIG. 7 shows the fields of a TP4 header which builds on a CLNP header.
FIG. 8 shows a Content-Addressable Memory (CAM) as being employed
in the Protocol Filter of the first embodiment.
10 FIG. 9 shows a block diagram of the Protocol Filter in accordance with
the first embodiment of the present invention.
FIG. 10A shows a connection identifier distinguished by means of the
present Protocol Filter.
FIG. 10B shows a connection identifier distinguished by means of the
present Protocol Filter.
FIG. 11 shows a connection index distinguished by means of the present
Protocol Filter.
FIG. 12 shows a block diagram of the Protocol Filter as part of a
Multiprotocol Router, in accordance with the second embodiment
of the present invention.
FIG. 13 shows a schematic block diagram of the Protocol Filter as part of
a Multimedia Workstation.
FIG. 14 shows a schematic block diagram of the Protocoi Filter as part of
a Server.
WO 94/22253 ~ 1 ~ 8 013 7 PCT/EP93/00677
GENERAL DESCRIPTION
When exchanging or transmitting information, e.g. data packets or multimedia
data streams, in or along a network, the transmission or exchange builds on
5 multiple protocol types. The protocol information of the different protocol
types is inserted into a protocol header of a data packet or data stream to be
transmitted .
This protocol header has to be received and processed prior to routing the
attached data stream through a switch or a network, prior to compressing
incoming traffic, or prior to multiplexing it. The processing of headers, in
particular the processing of the protocol related words therein, typically takesplace in network nodes, adapters, bridges, multiplexers. compressors,
protocol analyzers, and switches, but also in servers, just to name some of the
15 conceivable environments.
In connection with the first embodiment, the basic concept of the present
invention will be described. The inventive Protocol Filter (PF) 10 is shown in
Figure 1. By means of the PF 10, processing of protocols is much simpler,
20 since connection identification of layered protocol headers - in accordance
with the inventive method - when being implemented in hardware, is much
faster. The function of the Protocol Filter 10 is to extract the relevant
information from the protocol header of a received data stream or packet, to
compare this information with stored connection information and to provide
25 the associated connection identifier if both data are equal. In the present
embodiment, PF 10 is employed in a Token-Ring network adapter 14 to extract
all relevant words from the fields 22 - 27 of a protocol header 20 preceding a
data stream 21, received via bus 11, as schematically illustrated in Figure 2.
At an output port 12, a connection identifier is provided which can be used for
30 further processing. This further processing depends on the environment in
which the Protocol Filter 10 is used.
WO 94/~ ~53 PCT/EW3/00677
As schematically illustrated in Figure 2, the data stream 21 is preceded by
said protocol header 20. In this simplified Figure, the header 20 comprises
fields 22, 23, and 24 which belong to a first p~otocol and fields 25 through 27
belonging to a second protocol which builds on said first protocol. In this
5 Figure, fields comprising protocol information being relevant for the
processing of tl-e respective data stream 21 are hatched.
The Protocol Filter 10 of the first embodiment, as part of said Token-Ring
adapter 14, is employed in a Token-Ring network carrying TCPIIP, ST-II, and
1O ISO CLNP/TP4 traffic. Details of said network are described in "IBM
Token-Ring Network: Architecture Reference", SC30-3374-02, third edition,
September 1989. The Token-Ring adapter 14 handles the Medium Access
Control (MAC) in its finite state machines. The LLC (Logical Link Control)
frames, in LPDU (Link Protocol Data Unit) format, received by the adapter 14
15 and to be processed by the Protocol Filter 10, are shown in Figure 3. The
DSAP (Destination Service Access Point) field 30 identifies the access point forwhich said LPDU is intended. Typical values of the DSAP field 30 are given in
the above mentioned "IBM Token-Ring Network: Architecture Reference",
SC30-3374-02. The DSAP value, i.e. the protocol-type information, is used as
20 starting point by the Protocol Filter 10 in the search through the different
protocol addresses. These protocol addresses are arranged in trees, in
accordance with the present invention. In the first embodiment, the TCP/IP
and ST-II addresses are part of a first tree shown in Figure 4, and the
addresses corresponding to the CLr~P/TP4 protocol are arranged in a second
25 tree, which is illustrated in Figure 5.
The addresses and protocol specific information used in the various layers of
the Internet Protocol (IP) form the tree shown in Figure 4. The first protocol
which builds on the Internet Protocol, i.e. the TCP/IP, is arranged on the left
30 hand side of Figure 4 and consists of four tree levels. A TCP/IP connection is
defined by the path through said tree (short-dashed) starting at the root 40 of
the tree characte-. izing the Protocol Type (= Internet) on which the TCP builds.
The first level defines the protocol version (Ver.Prot.) 41, the second level the
2~8~13
WO 94/22253 - PCT/EP93/00677
source address tS.Addr.) 43, followed by the destination address (D.Addr.) 44
and, at the fourth level, the source/destination port (S.D.P.) 45. This first path
defining the TCP/IP connection is stored in a Content-Addressable Memory of
the Protocol Filter 10, as will be described later. A second path (dashed)
5 defines a ST-II connection. This second path starts at the root 40 of the sametree and ends at the first level at 42. This second connection is solely definedby the protocol type (= Internet) and the protocol version (= #0052HID) in the
present example. This second path is stored in the PF 10, too. In the present
application, the # sign is used in connection with hexadecimal notation.
Figure 6A illustrates a TCP/IP header. The uppermost part of Figure 6A shows
the Internet Protocol header. The meaning of the abbreviations used in the IP
header fields are listed in the below given Table 1. The abbreviations of the
header fields 60 - 65 required for processing in the present Protocol Filter 10,15 i.e. carrying words comprising protocol information, are printed bold.
WO 94/22253 PCT/EP93/00677
2~ 58 ~1~ 1 o
-
Table 1: Internet Protocol header
Bits No.
Ver ~Protocol) Version 4 60
IHL Internet Header Length 4 61
TOS Type of Service 8 62
L Total Length 16
ID Identification 16
F Flags 3
FO Fragment Offset 13
TTL Time To Live 8
PROTO Protocol 8 63
HC Header Checksum 16
DA Destination Address 32 65
SA Source Address 32 64
The TCP part of the protocol header is illustrated in Figure 6A, too. The
abbreviations used in the fields of this TCP header are listed in Table 2. The
abbreviations of the relevant fields 66, 67 of the TCP header are printed bold.
WO 94/22253 2 ~ ~ ~ 11 PCTIEW3/00677
Table 2: TCP header
Bits No.
SP Source Port 16 66
DP Destination Port 16 67
SN Sequence Number 32
AN Acknowledge Number 32
DO Data Offset 4
RF ReservedlFlags 12
W Window 16
The content of the header fields of the IP header is defined in "Experimental
Internet Stream Protocol: Version 2 (ST-II)", RFC 1190, October 1990, edited
by C. Topolcic (in particular on page 75 thereof). The value of the IP Version
number (Ver; 60) is #4, the normal header length of the Internet header (IHL;
61) is #5 and the value of the Type Of Service field (TOS; 62) is #00, these
values being given in hexadecimal notation. The protocol field (PROTO; 63)
in IP holds an 8~bit number which is defined in "Assigned Numbers", J.
Postel, RFC 790, September 1981. This 8-bit number of the protocol field
(PROTO; 63) is #06. These four mentioned IP header fields 60 - 63 are
concatenated and padded to get a 32-bit word to be stored in the Protocol
Filter 10, in accordance with the present invention. This results in a 32-bit
word #00450006 in the present case defining the protocol version, herein
referred to as Ver.Prot. field 41, see first level of the tree given in Figure 4.
Source Address (SA; 64) and Destination Address (DA; 65) of said IP header
are equal to the addresses at 43 (S.Addr.) and 44 (D.Addr.) of the tree. The
format of the addresses being held in these two fields are also defined in
WO 94/22253 - PCTIEP93/00677
~8~
"Assigned Numbers", J. Postel, RFC 790, September 1981. The
source/destination port (S.D.P.) address 45 in the tree is derived from the
Source Port (SP; 66) field and the Destination Port (DP; 67) field of the TCP
header in Figure 6A. Details of TCP are given in the already mentioned
5 protocol specif~cation "Transmission Control Protocol; DARPA Internet
Program Protocol Specification", RFC 793, DARPA, September 1981. How
these four levels of the TCP/IP part of the tree, shown in Figure 4, are stored
in the Protocol Filter is shown in Figure 8.
10 The header of the second protocol, the ST-II protocol, derived from the
Internet Protocol, is illustrated in Figure 6B. The abbreviations are explained
in Table 3. Fields 68 - 70 carry protocol information being relevant.
~5 Table 3: ST-II header
Bits No.
ST IP Version number =5 4 68
Ver ST-Version number = 2 in case of ST-II 4 69
Pri Priority of the packet 3
T Time Stamp
L TotalBytes 16
HID Hop Identifier 16 70
HC Header Checksum 16
30 ST is the IP Version number assigned to ST packets and the Ver field 69
comprises the ST-Version number. The value for S1 is #5 and the value for
Ver is #2 in case of ST-II, as defined in "Experimental Internet Stream
Protocol; Version 2 (ST-II)", RFC 1190, October 1990, edited by C. Topolcic.
WO 94122253 2 ~ 5 8 0 13 13 PCT/EP93/00677
For ST-II, the content of the ST, Ver, and HID fields 68 - 70 is extracted from
the header and concatenated to the 32-bit word #0052HID, which is stored in
the present PF 10.
5 The respective frames of TP4 which builds on CLNP, as well as the frames
corresponding to CLNP are illustrated in Figure 7. The abbreviations
assigned to the respective frames of the CLNP packet header are explained
in Table 4.
Tsble 4: CLNP header
Bits No.
NLPI Network Layer Protocol Indicator 8 71
Ll Length Indicator 8
V/PIE Version/Protocol Id Extension 8 72
LT Life Time 8
F ~lag 3 73
Type 1ype: DT PDU 5 74
SL Segment Length 16
Chs Checksum 16
Next, some typical values of fields 71 - 74 of the CLNP header are given.
NLPI = #81 indicates that Version 1 of the respective protocol is used. The
value of V/PIE is #01. The value 11100 is assigned to the Type frame 74 in
case of DT PDU. The following fields of the CLNP header, NLPI =#81,
V/PIE=#01, F=X, and Type=Y are concatenated and padded to a 32-bit
word #008101XY. This word is herein referred to as CLNP Hdr 51, see
WO 94/22253 14 PCT/EP93/00677
~1 3gOl3
Figure 5. The meaning of the abbreviations used in the TP4 header fields is
shown in Table 5.
Table 5: TP4 header
Bits No.
Ll Length Indicator 16
DT Data 8 75
DR Destinationreference 16 76
TN TPDU Number and EOT Flags 8
The value of the Data field (DT; 75) of said TP4 header is 1111 0000 which is
equal to #F0 using hexadecimal notation. The Destinationreference (DR; 76)
is XXX>( resulting in a 3Z-bit word #F000XXXX, referred to as TP4 header (TP4
Hdr; 52). The characteristic 32-bit words CLNP Hdr 51 and TP4 Hdr 52 are
stored in the present Protocol Filter 10, as described below.
Referring now to Figure 8, a Content-Addressable Memory (CAM) 80 is
shown, which is part of the Protocol Filter 10. This CAM 80 is characterized
in that an address of a row which comprises a word is presented at the
output 82 each time a protocol information at its input 84, e.g. the word 83,
matches the word stored in a row. If for example the word #1000450006 is
applied to the CAM's input 84, the CAM provides the CAM address of the
respective row at its output 82 as soon as the word at the input 84 matches a
stored word. Since the CAM 80 of the present embodiment is a CAM having
256 rows, CAM addresses with 28 bits or two-digit hexadecimal addresses
are needed. In the given example the two digit-address #01, corresponding
to row 81, would be sent to the output 82. CAMs are described in
"Content-Addressable and Associative Mernory". L. Chisvim et al., IEEE
Computer, Jul~ 1989, pp. 51 - 63.
WO 94/22253 21~ 8 ~ 13 PCT/EW3/00677
.
As shown in Figure ~, the different paths are stored in the CAM. where a row
contains the information of a tree level (Tag), the protocol-type information
(PType) and the address infonnation (Hld). There are two possibilities in a
protocol filter to compare the protocol information with the CAM content. The
5 simplest way is to concatenate the header information to a concatenated
information word of width w, the width of a row of this CAM, and compare it
in one operatir.n with the rows of a CAM. This approach has the advantage
that it is easy to implement. The width of the CAM is determined by the
number of bits required when the maximal possible number of header
1O information are concatenated.
The tagged CAM 80, presented in the first embodiment, consumes less
memory space than a conventional CAM. The number of header words to be
scanned is 1, if for example a protocol soch as XTP, directly builds on the
15 Media Access Control (MAC), or at most 5 for the example on the left hand
side of Figure 4. Using the tagged CAM one takes advantage of the
hierarchical structure of the protocols and the protocol addresses. In Figure
8, an exemplary row 83 of the CAM is illustrated. The first section of this row
83 comprises a tag, alsn referred to as level number, being equal to the
20 respective level of one of the protocol trees of Figures 4 and 5. In the nextfield, to the right of the tag field, the respective protocol-type information
(PType) is stored, followed by an address such as for example the 32-bit
words Ver.Prot, D.Addr. and so on.
25 The interaction of the various units of the inventive Protocol Filter 10 withsaid tagged CAM 80 will now be described in connection with Figure 9. The
Protocol Filter 10 comprises the following four units: the already mentioned
Content-Addressable Memory (CAM) 80, a Protocol-Type Detector (PTD) 90, a
Mask Generator (IMG) 91, and a Connection Number Builder (CNB) 95.
The Protocol-Type Detector (PTD) 90 is a state machine which reads the
header protocol-type information on a bus 97, e.g. a Token-Ring, and extracts
the protocol-type information from an incoming protocol header. Next, the
WO 94/22253 ~ L ~ 8 ~ ~ ~ PCT/EP93/00677
16
PTD 90 forwards this protocol-type information to the Mask Generator (MG)
91. In case of a LLC header, illustrated in Figure 3, the PTD 90 extracts the
protocol-type information from the Destination Service Access Point tDSAP)
field 30 by looKing up the DSAP in a table. This table is a memory, not
shown, of the size 256 times t, with t being equal to the size of the protocol
type field 99 in the Mask Register (MG) 93 of the Mask Generator 91. The
DSAP is used as the address to read the protocol-type information in this
table .
10 The Mask Generator (MG) 91 consists of a Header State Machine (HSM) 94
and a Tag Counter (TC) 92. The HSM 94 is started by the PTD protocol-type
information and the HSM 94 sequentially reads the header fields provided via
bus 97. If a header field is reached which comprises information relevant for
the connection detection, i.e. for the processing of a data stream, it is written
15 to the field 100 of the Mask Register (MG) 93. As described above, the tag
determines the tree level for which a header word is valid. The Tag Counter
(TC) 92 is a c-bit counter which is incremented for each relevant field to be
compared and ~eset by the PTD 90. For TCP/IP and most other transport
protocol stacks a 2-bit counter is sufficient. In case of the IP header, see
20 Figure 6A, the protocol information 60 - 63 is concatenated in one 32-bit word
(#00450006), calied concatenated information word, and is compared with the
rows of the CAM 80 in one operation. The tag counter and the PTD type are
concatenated with the protocol information in the mask register 93. The tag
counter is stored in the tag field 98 of the MR 93. The size t of the protocol
25 type field 99 in said MR 93 depends on the number of different protocols
which must be processed. With 6 bits most of today's protocols can be
covered. With the PF 10 according to the first embodiment, processing of
two different protocol types, illustrated in Figures 4 and 5, is possible. In this
particular example, the length t of the protocol type field 99 is only 1 bit.
The CAM 80, has the same width (w = c ~ t + 32 Bits) as the MR 93. For a
match, the C~M address of the data is given out. In case that the word
#100052HID is situated in said MR 93, the content of the MR 93 matches with
WO 94/22253 21~ 8 013 PCT/EP93/00677
the content of the row stored under CAM address A=#05 (=0000 0101) and
the CAM address A=#05 will be provided at the CAM's output 82. Because
the protocol-type information and the tag is included in the mask register 93,
the CAM output at port 82 is unique for the specific protocol information,
protocol-type information and tree level. The CAM 80 can be written from
outside.
The Connection Number Builder (CNB) 95 reads the CAM addresses at the
output of CAM 80 and generates a unique connection identifier by
concatenating the CAM addresses of the present path through one of the
protocol trees. The CNB 95 is triggered by the Mask Generator 91 to read
the CAM output 82. If the CAM 80 does not find a match, the CNB 95 is reset
and the protocol information is unknown to the present PF 10, and must be
dealt with in software. This CNB 95 generates a unique connection identifier,
i.e. a unique number, out of the stacked protocol header of LLC/IP/TCP, see
short-dashed path in the IP tree of Figure 4, as set out in context with Figures10A and B. The 8-bit CAM addresses, referred to as Ver.Prot. 101, S.Addr.
102, D.Addr. 103, and S.D.P. 104, are concatenated to form one concatenated
information word 105. In case of the LLC/IP/TCP path the value of this word
is #01020304 in hexadecimal notation, as illustrated in Figure 10B. When
preceding this word by the protocol-type information, e.g. PType = #00 in
the present case, a unique connection identifier #0001020304 is assigned to
the present protocol stack.
When concatenating the CAM address of the CAM row in which the value
#0052HID, characterizing the ST-II protocol stack, is stored, the connection
number #0005 is obtained (A = #05 preceded by PType = #00).
The 32-bit word #008101XY, characteriziny the CLNP, header and the 32-bit
word assigned to the TP4 header are stored at addresses #07 and #08 of the
CAM 80. A unique connection identifier is generated by the CNB 95 when
concatenating these two 8-bit wide hexadecimal numbers preceded by a
number characterizing the protocol type (PType). This number characterizing
WO 94/22253 ~ 8 ~ 18 PCT/EP93/00677
the protocol type! referred to as protocol-type information, is #01 in the
present case. The value of the connection identifier is #010708.
In case of the TCP/IP protocol stack, the value of the Ver.Prot. field identifies
5 the respective protocol stack. The source addresses (S.Addr.), destination
addresses (D.Addr.) and the source/destination ports (S.D.P.) can each
identify up to Z~6 addresses. To use the connection identifier as a pointer in
an array of connection control blocks, the 32-bit connection identifier must be
converted to a connection index. This can be done in the following,
10 exemplary way: The first byte, given in the Ver.Prot. field 101, is used as apointer to the array of control blocks of the specific protocol version, in thisexample the TCPIIP control block. The 8-bit addresses are different, because
each address codes an identifier in another tree level. Therefore only bj bits
of the 8 bits are needed to distinguish 2bi addresses in a tree level i. The
15 connection index is çlenerated by extracting the bj bits in each address and
concatenating them. The CAM must be written such that all addresses of the
same protocol type and tree level i are dTfferent in the least significant
bits b j.
20 If, for example, 8 source IP addresses, 4 destination addresses, and 8
source/destination addresses are reserved to generate a connection index,
they can be coded in 3, 2, and 3 bits, respectively. The 2- and 3-bit identifiers
of the 8 bit wide words 110 - 112 are concatenated to an 8-bit connection
index 113, shown in Figure 11. In this example, 20 entries in CAM 80 are
25 used for TCP/IP, the remaining 236 are free for other protocols. If the
maximal number of address entries at level i is allowed to dynamically
increase and 2b' ' addresses of level i must be distinguished, then all
addresses used for tree level i must be examined to guarantee that they are
different in the ieast significant bj ~ 1 bits. 1he size of the connection index30 113 is increased by one bit. Therefor a table, called routing table, must be
built, which holds the pointers to the control blocks, and the connection index
is used as a po,nter to this table. The generation of a connection index and
215~13
WO 94/22253 - PCT/EP93/00677
19
the management of the CAM is performed by a protocol processor to keep
the architecture flexible.
O Many protocol connections use less than four tree levels. The ST-II for
5 example uses only the protocol type and stream identifier given in the fields
40 and 42 of the tree in Figure 4. The resulting connection identifier has 16
significant bits and can be used directly by the Token-Ring adapter 14 to
detect multimedia data and to handle these data in dedicated devices.
Prior to describing other embodiments of the present invention, the
advantage of a t2gged CAM in view of conventional CAMs is addressed.
There are three possibilities in a Protocol Filter to compare the necessary
protocol information with the CAM content. The simplest way is to
concatenate the protocol information, the words comprising protocol-type
15 information and a tag (level number) to a concatenated information word of
width w, as described in connection with the first embodiment. This
approach makes use of the hierarchical structure of the 'protocol trees'. The
second approach, which is easy to implement, is characterized in that all
relevant protocol information of a protocol header is concatenated to form
20 one word of the width k. The width k of the CAM is determined by number of
bits required when the maximal possible number of header information is
concatenated. The number of bits required, for example, for TCP/IP over
LLC-Type 1, as illustrated in Figure 6A, is 12&, as shown in Table 6.
WO 94/22253 PCT/EP93/00677
ZO
Table 6: TCP/IP/LLC
Bits
S.Addr. 32
D.Addr. 32
S.D.P. 3Z
Version/Type 8
Protocol 8
LLC DSAP 8
LLC SSAP 8
total bits per row (k) 128
To support 256 connections 256 CAM rows with a total of 32768 bits are
required. The header information is extracted in a similar fashion as in the
Protocol Type Detector (PTD) and the Mask Generator (MG).
The third approach is to sequentially apply word by word, each carrying
25 address information, read from the protocol header to the input of a CAM.
According to this approach it is neither necessary to concatenate header
words prior to applying them to the CAM nor to store information in said
CAM in reflecting the hierarchical structure of the 'protocol trees'.
30 The tagged CAM 80, presented in connection with the first embodiment,
consumes less memory space as the two other approaches. The number of
header fields which have to be scanned is 1 if, for example, XTP directly
builds on the MAC (Media Access Control), or at most 5 for the example in
~ 8 0 ~ 3
WO 941~53 ~ PCT~P93/00677
21
Figure 4. By using the tagged approach one takes advantage of the
hierarchical structure of the protocols and the protocol addresses. Because
of the integration of the tag information into the Mask Register (MR) 93, up to
four levels are compared. The memory space consumed for the 256 TCP/IP
connections in the example is 800 bit, i.e. 20 times the CAM width of 40 bits.
For 256 XTP connections 256 rows with a total of 10240 bits are consumed.
In connection with the second embodiment of the present invention a
Protocol Filter 120, being part of a Multiprotocol Router 124, is described.
10 This Multiprotocol Router 124 comprises a Routing Table (RT) 125 and a
Routing Engine (RE) 127, as illustrated in Figure 12. For simplicity reasons,
the second embodiment is restricted to four different protocols; Internet
Protocol (IP), System Network Architecture (SNA), Netbios (Local Area
Network Basic Input/Output System), and OSI (Open Systems
15 Interconnection). In case that a data stream is received via input 121, said
Protocol Filter 120 scans this data stream and extracts the protocol-type
information thereof. Next, all relevant protocol header fields are scanned
and read. The information of these fields is preceded by said protocol-type
information and tagged using a level number generated by a Tag Counter.
20 Then, identicai entries in a tagged CAM are looked for, and the respective
CAM addresses provided at the CAM's output are concatenated to form a
unique connection identifier. Either this unique connection identifier, or a
connection index distinguished thereof, is forwarded via link 122 to a Routing
Table 125. With aid of the routing information of this table 125, a Routing
25 Engine (RE, 127) starts processing of the data stream whose protocol header
has been scanned and processed by the Protocol Filter 120 in the meanwhile.
The use of the present method and apparatus is not limited to the two
embodiments described above. Further applications are schematically
30 illustrated in Figures 13 and 14. In Figure 13, the Protocol Filter 130 is
shown as part of a multimedia protocol adapter used to separate audio,
video and traditional data received. The unique connection identifier is
forwarded to a Stream Demultiplexer (SD) 131 for separation of the different
WO 94/22253 2Z PCT/EP93/00677
data streams. In Figure 14, a Protocol Filter 140 is shown being connected to
a server 142. The data stream received, as well as the unique connection
identifier, is forwarded to a Protocol Processor (PP) 141 for further
processing .
The Protocol Filter can also be used in a light-weight Multimedia Adapter to
separate isochronous and asynchronous data streams and to trigger units for
checksumming, decryption and decompression of data. Such a Multimedia
Adapter at least comprises a Medium-Access Control (MAC) Unit, a
Checksumm Unit, a Direct-Memory Access (DMA) Unit and the Protocol
Filter.
In addition to the embodiments and applications mentioned, it is
advantageous to employ a Protocol Filter, in accordance with the present
15 invention, in a Protocol Analyzer, also referred to as Protocol Sniffer, which
can be plugged to a network, wherever a problem occurs, for monitoring
reasons .
Typical environments for the present Protocol Filter are FDDI (Fiber
20 Distributed Data Interface), ATM (Asyncronous Transfer Mode), and FCS
(Fiber Channel Standard) networks.
