Cascading associative memory arrangement

Details Cascading associative memory arrangement Cascading associative memory arrangement

2000-06-22

2003-12-02

Coulter, Kenneth R. (Department: 2152)

Electrical computers and digital processing systems: multicomput

Multicomputer data transferring via shared memory

Partitioned shared memory

C709S206000

Reexamination Certificate

active

06658458

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to computer networks, and more specifically, to a method and apparatus for configuring a memory device to efficiently perform matches against long input strings, such as network messages.
2. Background Information
A computer network typically comprises a plurality of interconnected entities that transmit (i.e., “source”) or receive (i.e., “sink”) data frames. A common type of computer network is a local area network (“LAN”) which typically refers to a privately owned network within a single building or campus. LANs employ a data communication protocol (LAN standard), such as Ethernet, FDDI or Token Ring, that defines the functions performed by the data link and physical layers of a communications architecture (i.e., a protocol stack), such as the Open Systems Interconnection (OSI) Reference Model. In many instances, multiple LANs may be interconnected by to form a wide area network (“WAN”), metropolitan area network (“MAN”) or intranet. These LANs and/or WANs, moreover, may be coupled through one or more gateways to the Internet.
Each network entity often includes network communication software, which operates in accordance with the Transmission Control Protocol/Internet Protocol (TCP/IP). TCP/IP basically consists of a set of rules defining how entities interact with each other. In particular, TCP/IP defines a series of communication layers, including a transport layer and a network layer. At the transport layer, TCP/IP includes both the User Datagram Protocol (UDP), which is a connectionless transport protocol, and the Transmission Control Protocol (TCP) which is a reliable, connection-oriented transport protocol. When a process at one network entity wishes to communicate with another entity, it formulates one or more messages and passes them to the upper layer of its TCP/IP communication stack. These messages are passed down through each layer of the stack where they are encapsulated into packets and frames. Each layer also adds information in the form of a header to the messages. The frames are then transmitted over the network links as bits. At the destination entity, the bits are re-assembled and passed up the layers of the destination entity's communication stack. At each layer, the corresponding message headers are stripped off, thereby recovering the original message which is handed to the receiving process.
One or more intermediate network devices are often used to couple LANs together and allow the corresponding entities to exchange information. For example, a bridge may be used to provide a “bridging” function between two or more LANs. Alternatively, a switch may be utilized to provide a “switching” function for transferring information, such as data frames or packets, among entities of a computer network. Typically, the switch is a computer having a plurality of ports that couple the switch to several LANs and to other switches. The switching function includes receiving messages at a source port and transferring them to at least one destination port for receipt by another entity. Switches may operate at various levels of the communication stack. For example, a switch may operate at layer
2
which, in the OSI Reference Model, is called the data link layer and includes the Logical Link Control (LLC) and Media Access Control (MAC) sub-layers.
Other intermediate devices, commonly referred to as routers, may operate at higher communication layers, such as layer
3
which, in TCP/IP networks corresponds to the Internet Protocol (IP) layer. IP message packets include a corresponding header which contains an IP source address and an IP destination address. Routers or layer
3
switches may re-assemble or convert received data frames from one LAN standard (e.g., Ethernet) to another (e.g. Token Ring). Thus, layer
3
devices are often used to interconnect dissimilar subnetworks. Some layer
3
intermediate network devices may also examine the transport layer headers of received messages to identify the corresponding TCP or UDP port numbers being utilized by the corresponding network entities. Such extended-capability devices are often referred to as Layer
4
, Layer
5
, Layer
6
or Layer
7
switches or Network Appliances. Many applications are assigned specific, fixed TCP and/or UDP port numbers in accordance with Request for Comments (RFC) 1700. For example, TCP/UDP port number
80
corresponds to the hyper text transport protocol (HTTP), while port number
21
corresponds to file transfer protocol (ftp) service.
FIG. 1
is a partial block diagram of a Network Layer packet
100
corresponding to the Internet Protocol. Packet
100
includes a protocol field
104
, an IP source address (SA) field
106
, an IP destination address (DA) field
108
and a data field
110
, among others.
FIG. 2
is a partial block diagram of a Transport Layer packet
200
. Packet
200
includes a source port field
202
, a destination port field
204
and a data field
206
, among others. As indicated above, Fields
202
and
204
identify the local end points of the connection between the communicating entities and may include flow information and certain predefined or dynamically agreed-upon TCP or UDP port numbers.
Access Control Lists
Some networking software, including the Internetwork Operating System (IOS®) from Cisco Systems, Inc., supports the creation of access control lists or filters, which are typically used to prevent certain traffic from entering or exiting a network. In particular, certain layer
3
intermediate devices utilize access control lists to decide whether received messages should be forwarded or filtered (i.e., dropped) based on certain pre-defined criteria. The criteria may be IP source address, IP destination address, or upper-layer application based on TCP/UDP port numbers. For example, an access control list may allow e-mail to be forwarded, but cause all Telnet traffic to be dropped. Access control lists may be established for both inbound and outbound traffic and are most commonly configured at border devices (i.e., gateways or firewalls) to provide security to the network.
To generate an access control list, a network administrator typically defines a sequence of criteria statements using a conventional text editor or graphical user interface (GUI). As each subsequent statement is defined, it is appended to the end of the list. The completed list is then downloaded to the desired layer
3
intermediate device where it may be stored in the device's non-volatile RAM (NVRAM) typically as a linked list. Upon initialization, the intermediate device copies the access control list to its dynamic memory. When a packet is subsequently received at a given interface of the device, a software module of IOS® tests the received packet against each criteria statement in the list. That is, the statements are checked in the order presented by the list. Once a match is found, the corresponding decision or action (e.g., permit or deny) is returned and applied to the packet. In other words, following a match, no more criteria statements are checked. Accordingly, at the end of each access control list a “deny all traffic” statement is often added. Thus, if a given packet does not match any of the previous criteria statements, the packet will be discarded.
Currently, access control lists are used primarily to provide security. Thus, for a given interface, only a single list is evaluated per direction. The lists, moreover, are relatively short. Nevertheless, the evaluation of such lists by software modules can significantly degrade the intermediate device's performance (e.g., number of packets processed per second). This degradation in performance has been accepted mainly due to a lack of acceptable alternatives. It is proposed, however, to expand the use of access control lists for additional features besides just security decisions. For example, access control lists may also be used to determine whether a given packet should be encrypted and/or whether a particular qual

Affiliated with

Also associated with

Rating

Cascading associative memory arrangement does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Cascading associative memory arrangement, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cascading associative memory arrangement will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3123817