Look-up engine for packet-based network

Details Look-up engine for packet-based network Look-up engine for packet-based network

1996-08-16

1999-06-29

Nguyen, Chau

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

370401, H04L 1246

Patent

active

059178213

DESCRIPTION:

BRIEF SUMMARY
BACKGROUND OF THE INVENTION



FIELD OF THE INVENTION

This invention relates to the field of data communications, and more particularly to packet-based digital communications networks.
There are two broad classes of network: circuit-based and packet-based. Conventional telephone networks are circuit based. When a call is established in a circuit-based network, a hard-wired connection is set up between the calling parties and remains in place for the duration of the call. Circuit-based networks are wasteful of available bandwidth and lack flexibility.
Packet-based networks overcome many of the disadvantages of circuit-based networks. In a packet-based network, the data are assembled into packets containing one or more address fields which define the context of a packet, such as protocol type and relative positions of other fields embedded in the packet. LAN bridges and routers use the information in the packet to forward it to the destination.
In a packet-based network, a packet must be parsed as it flows through the network. Parsing is the process of extracting and analyzing the information, such as source and destination address and net layer protocol, contained in the packets.
In known networks, packet parsing is generally performed with a microprocessor, which provides flexibility in handling different packet types and can be upgraded to handle new packet types as they are defined. Content Addressable Memory (CAM) is commonly used for hardware assistance to speed up searches through a list of known addresses. This is a tedious task. CAMs are also relatively expensive and limited in size and availability.
General purpose processor architectures are not specifically directed toward the types of operations required in packet parsing and so they tend to be inefficient. To meet performance requirements, a fast but expensive processor based solution can be implemented. In the highest performance systems, hardware solutions are implemented to increase speed, but at the cost of flexibility.


SUMMARY OF THE INVENTION

An object of the invention is to provide a fast, but inexpensive solution to the problem of packet-parsing in packet-based networks.
According to the present invention there is provided an arrangement for parsing packets in a packet-based digital communications network, said packets including packet headers divided into fields having values representing information pertaining to the packet, said arrangement comprising an input memory for receiving fields from said packet headers of incoming packets; and a look-up engine for retrieving stored information appropriate to a received field value. The look-up engine includes at least one memory storing information related to possible values of said fields in a hierarchical tree structure and associated with a respective field of packet headers; a memory controller associated with each said memory storing information related to possible values of said fields for controlling the operation thereof to retrieve said stored information therefrom; and a microcode controller for parsing a remaining portion of the packet header while said stored information is retrieved and controlling the overall operation of said look-up engine.
The memory and retrieving means constitute a look-up engine, which is the central resource containing all information necessary for forwarding decisions. In a preferred embodiment the look-up engine includes a source address look-up engine and a destination address look-up engine.
In a packetized data transmission conforming to IEEE802 standards, the packets have a MAC (medium access control) header containing information about the destination and source addresses and the net layer protocol. The invention permits packet switching to be achieved in a bridge-router, for example an Ethernet to ATM bridge-router, at a rate of about 178,000 packets per second using 64 byte minimum Ethernet packets. This means that the MAC headers are interpreted once every 5.6 micro seconds.
The look-up engine preferably employs table look-ups using nibble

REFERENCES:
patent: 5095480 (1992-03-01), Fenner
patent: 5463777 (1995-10-01), Bialkowski et al.

Affiliated with

Also associated with

Rating

Look-up engine for packet-based network does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Look-up engine for packet-based network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Look-up engine for packet-based network will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1382599