Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-09-02
2001-09-11
Ngo, Ricky (Department: 2731)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C713S154000
Reexamination Certificate
active
06289013
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to packet forwarding engines used in telecommunications, and, in particular, to router algorithms and architectures for supporting packet filter operations with reduced memory.
2. Description of the Related Art
Packet-based communication networks, such as the Internet, typically employ a known protocol over paths or links through the network. Commonly known protocols are, for example, Transmission Control Protocol/Internet Protocol (TCP/IP) or Reservation Set-up Protocol (RSVP). Routers provided in a communication network provide a packet forwarding function whereby input data, usually in the form of one or more data packets, is switched or routed to a further destination along a network link.
FIG. 1
shows a typical form of a data packet
20
, which may be of variable length. Data packet
20
comprises, for example, a header
125
and payload data
150
. Header
125
contains fields or parameters, such as a source address
130
where said data originate and one or more destination addresses
135
where the data is to be routed. Typically, a data packet
20
contains a single destination address. Another parameter in the header
125
may be a protocol type
140
identifying a particular protocol, such as TCP, employed in the communication network.
FIG. 2
shows a router
245
of a network node receiving streams or flows of data packets from input links
247
and routing these packet streams or flows to output links
260
. To perform a forwarding function, router
245
receives a data packet at an input link
247
and a control mechanism
250
within the router utilizes an independently generated look-up table (not shown) to determine to which output link
260
the packet should be routed. It is understood that the packet may first be queued in buffers
252
before being routed, and that the forwarding function is desirably performed at a high rate for high forwarding throughput.
Source and destination addresses may indicate end hosts (not shown). Thus, data packet
20
of
FIG. 1
may further comprise unique source port numbers
137
and destination port numbers
139
. Header
125
may also include, for example, certain types of flags (not shown), depending upon the receiver or transmitter application.
Network service providers, while using a shared backbone infrastructure, may provide different services to different customers based on different requirements. Such requirements may be: different service pricing, security, or Quality of Service (QoS). To provide these differentiated services, routers typically include a mechanism for 1) classifying and/or isolating traffic, or packet flows, from different customers, 2) preventing unauthorized users from accessing specific parts of the network, and 3) providing customized performance and bandwidth in accordance with customer expectations and pricing.
Consequently, in addition to the packet forwarding function, router
245
of
FIG. 2
may perform a packet filtering function. Packet filtering may be employed, for example, as “firewall protection” to prevent data or other information from being routed to certain specified destinations within the network. To perform packet filtering, the router
245
may be provided with a table or list of filter rules specifying routing of packets. For example, packets sent from one or more of specified sources may be denied or specific action may be taken for those packets having a specified source address. This packet filtering may be employed for layer four switching applications.
Specifically, packet filtering parses fields from the packet header
125
including, for example, both the source and destination addresses. Parsing allows each incoming packet to be classified using filter rules defined by network management software, routing protocols, or real-time reservation protocols such as RSVP.
Filter rules may also specify, for example, that received packets with fields specifying that a particular destination address should or should not be forwarded through specific output links, or that some other specific action should be taken before routing such received packets. Thus, a variety of filter rules may be implemented based on packet field information. For example, such filter rules might be based on 1) source addresses; 2) destination addresses; 3) source ports; 4) destination ports; and/or 5) any combination of these fields.
Packet filtering of the prior art generally requires either an exact match operation of the fields or a match operation defined in terms of field ranges for a filter rule. Field ranges may specify, for example, ranges of source addresses, destination addresses, source/destination port numbers, and/or protocol types. Filter rules are then applied to every packet that the router receives; that is, for each packet received by the router, every filter rule is successively applied to each packet to ascertain whether that packet is to be forwarded, restricted, or re-routed according to the filter rule. However, implementation of a large number of filter rules in a router (e.g. 500 or more) is time consuming since all filter rules must be tested. Hence, routers implementing filters having a large number of filter rules have decreased throughput, compromising a quality of service (QoS). Thus, for a router such as router
245
to maintain a relatively high level of throughput, the filtering function must be performed at very high rate with no queuing before field processing.
The IP packet header fields may each contain up to 128 bits of parameter information, including source and destination addresses, physical source and destination port numbers, interface number, protocol type, etc. Each of the fields or parameters in the header may be represented as being along an axis of a dimension. The general packet classification problem of a packet filter may then be modeled as a point-location in a multi-dimensional space. One or more field values of a packet defines a point in the multi-dimensional space. A packet filter rule associated with a range of values of each defines an object in the multi-dimensional space.
A point-location algorithm in a multi-dimensional space including multi-dimensional objects finds the object that a particular point belongs to. In other words, given a received point E
j
={E
1
, E
2
, . . . E
D
} in a space having D dimensions, find one or more of a set of n D-dimensional objects including the point (n being an integer greater then 0). The general case of D>3 dimensions may be considered for the problem of packet classification. As is known in the art the best algorithms optimized with respect to time or space have either an O(log
D−1
n) time complexity with O(n) space or an O(log n) time complexity with O(n
D
) space. Here, O(•) mathematically represents “on the order of.” Comparing algorithms on the basis of the order of operations is particularly useful since operations may be related to memory requirements (space) and execution time (time complexity).
Though algorithms with these complexity bounds are useful in many applications, they are not currently useful for packet filtering. First, packet filtering must complete within a specified amount of time, which generally forces n to be relatively small relative to asymptotic bounds, but routers must filter packets with a number of filter rules in the range of a few thousand to tens of thousands. Consequently, even point-location algorithms with poly-logarithmic time bounds are not practical for use in a high-speed router.
For example, router
245
may desirably processes n=1K filter rules of D=5 dimensions within 1 &mgr;s to sustain a 1 million-packets-per-second throughput. However, an algorithm employed with O(log
D−1
n) complexity and O(n) space has a log
4
1024 execution time and O(1024) space, which requires 10K memory accesses (look-ups) per packet. If an O(log n) time O(n
4
) space algorithm is employed, then the space requirement becomes prohibitivel
Lakshman T. V.
Stiliadis Dimitrios
Hughes Ian M.
Lucent Technologies - Inc.
Mendelsohn Steve
Ngo Ricky
LandOfFree
Packet filter method and apparatus employing reduced memory does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Packet filter method and apparatus employing reduced memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Packet filter method and apparatus employing reduced memory will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2496005