US20020007360A1 - Apparatus and method for classifying information received by a communications system - Google Patents

Abstract

The present invention involves a system and method for classifying information received by a communications device. A first parameter having a first parameter range and a second parameter range, and a second parameter having a third parameter range and a fourth parameter range, are defined. A first class having one of the first parameter and the second parameter ranges, and one of the third and the fourth parameter ranges, are also defined. A second class having another one of the first parameter and the second parameter ranges, and another one of the third and the fourth parameter ranges, is also defined. Information having a first parameter value and a second parameter value is received. The method determines if the first parameter value is within one of the first and second parameter ranges and if the second parameter value is within one of the third and fourth parameter ranges is made. If so, the information is classified into one of the first and second classes based on the first parameter value and the second parameter value, otherwise the information is classified as a default class. An output value representative of the classification is then generated.

Description

BACKGROUND OF THE INVENTION
• [0001]1. Field of the Invention
• The present invention relates generally to communication devices, and specifically, to an apparatus and method for classifying information received by communications devices.[0002]
• [0003]2. Background Information
• Small and medium businesses typically have networks comprised of local area networks (“LANs”), ranging between 10 Mega bits per second (“Mbps”) to 100 Mbps, that carry information between stations for a wide range of applications. The applications can include a mixture of voice, video, interactive, web browsing, file transfers, etc., each of which has different minimum requirements for latency, jitter, and data loss to ensure quality communication. The internal office LANs can either provide sufficient bandwidth or are economically upgradable to provide an order of magnitude increase in bandwidth.[0004]
• The connection to a wide area network (“WAN”) is however another matter. The bandwidth is not easily upgradable due to the cost of WAN access circuits. Various queuing techniques have been employed in WAN access equipment in attempts to provide sharing of the limited circuit bandwidth among the different types of data. These queuing techniques typically have limited applications and undesirable characteristics. For example, in one queuing technique, queues are serviced in strict priority order, which tends to starve low priority data types. Another technique, called Weighted Fair Queuing, solves the starvation effects but it is computational intensive and does not provide guaranteed bandwidth, delay bound or jitter bound characteristics for data types that need these characteristics.[0005]
• In implementing such queuing techniques, incoming data must first been identified and thereafter, classified for queuing allocation. Current routers, which provide some form of classification system, do so by combining search technologies previously used for routing table lookups. These technologies rely on algorithms such as the Patricia tree (as described by Don Morrison in “Practical Algorithm to Retrieve Information Coded In Alfanumeric,” Journal of the ACM, October[0006]1968), or the Lulea tree (as described by Mikael Degermark of the Lulea University of Technology in “Small Forwarding Tables for Fast Routing Lookups,” Computer Communications Review, October1998), search algorithms to perform lookup operations of various portions of the internet protocol (IP) header. The results from these searches are combined in some fashion (e.g., using Cross Product tables or arrays, as described by V. Srinivasan of Washington University in “Fast and Scalable Layer Four Switching,” Computer Communications Review, October1998) and used to formulate a “class” for the incoming data.
• Existing routing search algorithms are used to handling definitions of the form “Address A=route n”. To apply an existing routing search technique for searching and classifying data in ranges, “n” individual search steps have to be used. This results in excess data storage space requirements, and additional processing requirements when handling classification ranges.[0007]
• Since the number of possible resulting combinations can be immense, the problem of translating the search results to a “class” is not trivial. Traditional approaches use either a simple array or something like a Cross Product table (as described by V. Srinivasan of Washington University in “Fast and Scalable Layer Four Switching,” Computer Communications Review, October[0008]1998.
• Simple arrays, although fast, require memory to hold every possible combination, so are impractical except for the simplest cases. The problem associated with using Cross Product tables to locate the final “class” results is that the most recently accessed results must be cached in the Cross Product table. Basically, the results from each individual search are combined by an expression similar to “finalResult=(((((((result[0009]1* maxResultl)+result2)*maxResult2)+result3)*maxResult3)+result4)*maxResult4)+result5”. The final “cross product” value is searched for in the “key” column of the Cross Product table, using a binary search. If the value is found, the correspond “result” column entry is returned as the “class” value. If not found, which is more likely to be the case due to the large range of possible values, a exhaustive search of the available classes must be done. The found “class” and the “cross product” value are both added to the “Cross Product” table. Although a Cross Product table does minimize the amount of memory required, processing requirements become nondeterministic.
• Accordingly, there is a need in the technology for classifying incoming data received by a communications device that overcomes the aforementioned problems.[0010]
• To classify incoming data, searches are typically performed to identify incoming data such as network frames or protocol data units. Traditional search methods either required each unique value to be explicitly stored in a search tree, or required an elaborate tree structure such as the use of a “grid of tries” to provide an efficient search. Since the search has to operate very quickly (typically less than one microsecond on the average), it is imperative to utilize the full capabilities of the processor in the communications device. For such traditional search techniques to operate efficiently, all data that has to be searched is typically stored in the processor's memory space. However, since the processor has only limited amounts of internal memory, the implementation of such traditional search techniques are not practicable.[0011]
• Moreover, such in using such traditional search techniques, the average and worst case execution times do not remain deterministic beyond a small number of search values. These values are those that are located in the processor's memory space.[0012]
• Accordingly, there is a need in the technology for an apparatus and method for identifying incoming data received by a communications device that overcomes the aforementioned problems.[0013]
SUMMARY OF THE INVENTION
• The present invention involves a system and method for classifying information received by a communications device. A first parameter having a first parameter range and a second parameter range, and a second parameter having a third parameter range and a fourth parameter range, are defined. A first class having one of the first parameter and the second parameter ranges, and one of the third and the fourth parameter ranges, are also defined. A second class having another one of the first parameter and the second parameter ranges, and another one of the third and the fourth parameter ranges, is also defined. Information having a first parameter value and a second parameter value is received. The method determines if the first parameter value is within one of the first and second parameter ranges and if the second parameter value is within one of the third and fourth parameter ranges is made. If so, the information is classified into one of the first and second classes based on the first parameter value and the second parameter value, otherwise the information is classified as a default class. An output value representative of the classification is then generated.[0014]
BRIEF DESCRIPTION OF THE DRAWINGS
• FIG. 1 illustrates an embodiment of a communication device suitable for use with embodiments of the present invention.[0015]
• FIG. 2 illustrates functional blocks within a queuing[0016]module200 according to one embodiment of the present invention.
• FIG. 3A illustrates one embodiment of the classification technique provided in accordance with the principles of the invention.[0017]
• FIG. 3B illustrates one example of Axis Preprocessing technique provided in accordance with the principles of the invention.[0018]
• FIG. 4 illustrates details of functional blocks within the flow classification and[0019]routing block218 according to one embodiment of the invention.
• FIG. 5A illustrates one embodiment of a search process flow provided in accordance with the principles of the present invention.[0020]
• FIG. 5B is a diagram that illustrates one example of the search process of FIG. 5A.[0021]
DETAILED DESCRIPTION
• The present invention thus provides a classification system and method by implementing an Axis Preprocessing classification technique in combination with a Binary Range Tree searching technique. The Binary Range Tree searching technique allows large ranges of contiguous values to be search using a minimal number of tree “nodes”, while the Axis Preprocessing technique assures that the maximum number of contiguous ranges is generated in the final “class” search step.[0022]
• FIG. 1 illustrates an embodiment of a[0023]communication device100 suitable for use with embodiments of the present invention. In one embodiment, thecommunication device100 is a quality of service access communications device. Referring to FIG. 1, thecommunication device100 includes a central processing unit (“CPU”)105 such as a microprocessor, microcontroller, or digital signal processor having on chip instruction anddata memory108 and110 (e.g., static random access memory “SRAM”), which are cache-like devices. The CPU105 is coupled to a plurality of devices by way of asystem bus115. In particular, the CPU105 is coupled to an external memory120 (e.g., Synchronous Burst SRAM, Synchronous Dynamic RAM, etc., or a combination of such devices), a FLASH memory device125 (e.g., 8 Mbytes) for downloading program information, and a battery backup SRAM130 (e.g., 2 Mbytes).
• In addition, a number of input/output (“I/O”) devices are coupled to the[0024]bus115, including an Ethernet media access control (“MAC”)port145 for receiving/transmitting data packets from/to aphysical interface150 and a plurality of T1/E1 framers160₁-160_X(where “X” is a positive whole number) for receiving/transmitting asynchronous transfer mode(“ATM”) cells and frames from/to respective I/O ports165₁-165_X. A field programmable gate array (“FPGA”)170 is coupled to thebus115. TheFPGA170 is also coupled to the T1/E1 framers160₁-160_Xand the CPU105 by way of aserial bus175. The control path of the T1/E1 framers160₁-160_Xand theFPGA170 is through the bus for configuring and reading status information from the devices. The data path (e.g., ATM cells, frames, etc.) to/from the ports is provided though theserial bus175. That is, data received from a port is transmitted to the CPU105 through theFPGA170 by way of theserial bus175, and data is transmitted to a port from the CPU105, though theFPGA170 by way of theserial bus175.
• Also coupled to the[0025]bus115 aregeneral purpose timers135, which are used for generating periodic interrupts, and direct memory access (“DMA”)controllers140 for transferring data from memory to memory, from the Ethernet MAC port buffer to memory, etc.
• When the[0026]communication device100 is powered up, anoperating system122 is loaded intomemory120 and/or theinstruction cache108 from a non-volatile storage device (e.g., FLASH125) or a mass storage device such as a hard disk drive (not shown). Also loaded intomemory120 and/or thedata cache110 is aconfiguration database124 having configuration information on virtual path connections (“VPCs”) and virtual circuit connections (“VCCs”) established for each user network interface (“UNI”). Thus, a user or organization wanting to communicate over a wide area network (“WAN”) will lease VPC and/or VCC services from a communication carrier. The communication carrier then establishes the VPC and/or VCC services for each UNI into thecommunication device100.
• A UNI is hereinafter used interchangeably with a port, with each port having one or more physical links. As discussed herein, a “data unit” refers to a packet, frame, or cell. A “flow” is defined as a uniquely identified stream of data units. Through inspection of data unit headers, the data units are categorized and classified to constitute a uniquely identified flow. In one embodiment, a flow is either a level-1 flow or a level-2 flow. Moreover, flows may be aggregated such that they are processed and managed as one aggregate flow. Thus, any reference to a flow refers to a flow or a flow aggregate. Processing and management of a flow includes allocating resources for the flow. Examples of resource allocation include link bandwidth allocation and node buffer allocation for a flow. An example of processing includes encapsulation of Internet Protocol (“IP”) datagrams with ATM request for comment (“RFC”) 1483 encapsulation, entitled “Multiprotocol Encapsulation over ATM Adaptation Layer 5”, published in July 1993. A protocol or protocol layer is hereinafter defined as a protocol that can be mapped into the Open System Interconnection (“OSI”) layer model.[0027]
• FIG. 2 illustrates functional blocks within a[0028]queuing module200 implemented on thecommunication device100 according to one embodiment of the present invention. Referring to FIG. 2, the functional blocks are broken up into three vertical segments, namely, receive, control, and transmit, and two horizontal segments, namely non-interrupt and interrupt functions. In one embodiment, thequeuing module200 is implemented in software, in which case, thequeuing module200 or portions thereof is contained in thememory120 and/orinternal memory108 of the CPU105, and is executed by the CPU105 (FIG. 1). For discussion purposes, thequeuing module200 is described as comprising a receive module, and a queue and transmit (QCT)module205.
Receive Segment
• In the receive segment, packets and frames such as, for example, IP packets, Ethernet frames, and frame relay frames are received by a packet/[0029]frame input function210. Theinput function210 performs preliminary filtering and cyclic redundancy checking (“CRC”) on the packets and frames. The packets and frames are then forwarded to a flow classification androuting block218.
• ATM cells are received by a[0030]cell input function212. Thecell input function212 determines whether there is an existing connection for the cell stream. The cells are then passed to an adaptationlayer processing block214 where the cells are converted to contiguous protocol data units (“PDUs”) using, for example, ATM adaptation layer 5 (“AAL5”). The adaptationlayer processing block214 also detects Integrated Local Management Interface (“ILMI”), Operations, Administration, and Maintenance (“OAM”), and signaling cells, and passes them directly to a supervision message system block220 for setting up/tearing down connections, etc. In addition, the adaptationlayer processing block214 detects resource management cells relating to flow control (e.g., ATM available bit rate “ABR” RM cells, etc.), and passes these cells to aresource manager block222 which then slows down or speeds up an existing flow in response to the management cells. After each PDU is reconstructed, it is passed to an ATMdecapsulation layer block216 where PDUs are decapsulated into data units using RFC1483. The ATMdecapsulation layer block216 then forwards the data units to the flow classification androuting block218.
• The flow classification and[0031]routing block218 determines whether a flow has been set up for an incoming data unit, and determines the class of traffic that the flow is assigned. If a flow has been set up for the packet, the packet and an associated Flow ID are transmitted to aforwarding block230 in the transmit segment. The Flow ID includes several components including a destination link, the shaping/scheduling parameters of the flow, the quality of service (“QoS”) parameters assigned to the flow, etc. Assignment of the Flow ID is dependent on the classification of the flow. The class assigned to the flow determines the QoS to be provided for that flow. In one embodiment, the Flow ID is an address pointing to a memory location where the aforementioned parameters are located. If a flow has not been assigned to the packet, the packet is sent to theforwarding block230 with a request that a flow be created for the packet at a desired QoS. Details of the flow classification androuting block218 will be described in detail in the following sections.
• In the case of VPC service, the VPCs are ordered and leased from a service provider. The VPC configuration associated with the VPC service ordered is then placed in the[0032]configuration database124 of the communication device100 (FIG. 1). The VPC may be manually configured, or automatically configured using protocols such as ILMI. In response to the VPCs ordered, thequeuing module200 sets up level-1 flows for the VPCs. Flow classification and policy definitions determine how to identify one protocol stream from another, in addition to the QoS parameters required to support each stream. As data units are received on an interface for a class where a flow has not been established, a level-2 flow is requested from a fly-by flowadmission control block232 via a forwarding application program interface (“API”) block230 based upon the flow classification and policy definition. When a level-2 flow is requested, it is requested with a corresponding level-1 Flow ID that was created by the user configuration. The flow classification androuting block218 use the configuration to determine routes and the set of level-1 flows available to make level-2 flows. Each level-2 flow created is assigned a level-2 Flow ID and a VCC. The VCC assignment allows flows to be multiplexed at the cell level (e.g., one cell from one flow followed by one cell from another flow).
• In the case of VCC service, the VCCs are also ordered and leased from the service provider. The VCC configuration associated with the VCC service ordered is then placed in the[0033]configuration database124 of the communication device100 (FIG. 1). This can be manually, or automatically configured using protocols such as ILMI. In response to the VCCs ordered, thequeuing module200 sets up level-1 flows for the VCCs. Flow classification and policy definitions determine how to identify one protocol stream from another and determine the QoS parameters required to support each stream. As data units are received on an interface for a class where a flow has not been established, a level-2 flow is requested from the fly-by flowadmission control block232 via the forwardingAPI block230 based upon the flow classification and policy definition. When a level-2 flow is requested, it is requested with a corresponding level-1 Flow ID that was created by the user configuration. The flow classification androuting block218 uses the configuration to determine routes and the set of level-1 flows available to make level-2 flows. Each level-2 flow created is assigned a Flow ID. VCC service does not assign VCCs to flows as in the VPC service. However, data structures for flow state machines are created and initialized as in VPC service. With VCC service, flows are multiplexed at the packet level (e.g., when a flow is chosen for output service, all segments of the packet are transmitted in consecutive succession before another flow is serviced).
Control Segment
• In the control segment, a connection management task[0034]226 (e.g., an ATM management task) and a physicalinterface management task228 are provided and run with/on the operating system122 (FIG. 1). These tasks operate in the non-interrupt code space and communicate with theresource manager222 by way of an API using thesupervision message system220. The API is used to pass messages (e.g., LMI, OAM, and signaling information) between the tasks and the WAN interface. Theresource manager222 sends requests for establishing, terminating, and modifying connections to theconnection management task226. Theconnection management task226 responds to such requests directing theresource manager222 to install, de-install, or modify the connections. The physicallayer management task228 communicates with theresource manager222, notifying the latter of the (up/down) status of physical ports. The LMI, OAM, and signaling messages passed back to thesupervision message system220 from theconnection management task226 are sent directly to a buffer management block234 for queuing inqueues236, and subsequent output.
• The[0035]resource manager222 handles the installation, de-installation, and modification of flows. This includes handling and generating resource management data to control the data rate for flow controlled connections such as, for example, ATM ABR. Theresource manager222 is also responsible for mapping class and policy definitions for the flows. Such class and policy definitions include resource requirements (e.g., bandwidth, peak rate limits, buffer delay, and jitter). Moreover, theresource manager222 assigns pre-established VCCs and flow state machine data structures for VPC service due to the activation/deactivation of the flows (e.g., layer-3 to layer-7 protocol flows such as IP). Activation of flows occurs upon data unit arrivals, or signaling protocols (e.g., ATM SVC Signaling or Resource RerserVation Protocol “RSVP”) that require a flow be established. Deactivation of flows occurs upon timeouts for flows (e.g., data unit arrivals not received for a predetermined amount of time), or by signaling protocols such as ATM SVC signaling and RSVP. Theresource manager222 is coupled to aflow database224 which contains the current resource state (e.g., available bandwidth for allocation, available buffers for allocation, etc.).
• In addition, the[0036]flow database224 includes other parameters and state variables including, but not limited or restricted to, Flow ID used to map, for example, a layer-3 protocol (e.g., IP) classified flow into a level-2 VCC, connection shaping parameters and state (e.g., QoS parameters such as peak and sustained bandwidth, maximum queuing delay, maximum burst size, etc.), and connection scheduling parameters and state (e.g., sustained rate). Theresource manager222 allocates resources for flows and keeps track of remaining resources using theflow database224. It determines whether resources can be allocated to flows and reclaims resources for flows no longer active.
• In the case of ATM, an example of a resource request to the[0037]resource manager222 may include the following:
• (1) ATM connection index;[0038]
• (2) ATM connection type (VPC or VCC);[0039]
• (3) Virtual path identifier (“VPI”);[0040]
• (4) Virtual connection identifier (“VCI”);[0041]
• (5) Traffic contract (e.g., ABR, UBR, VBR, CBR, GFR);[0042]
• (6) Peak cell rate (“PCR”);[0043]
• (7) Sustained cell rate (“SCR”);[0044]
• (8) Minimum cell rate (“MCR”);[0045]
• (9) Maximum cell burst size (“MBS”);[0046]
• (10) Associated routing virtual interface number;[0047]
• (11) Associated UNI number;[0048]
• (12) Buffer allocation (e.g., number of buffers);[0049]
• (13) ATM VCC endpoint function assignment (e.g., AAL5, AAL2, ILMI);[0050]
• (14) Encapsulation Type (e.g., 1483, null, etc.);[0051]
• (15) Hierarchy Level-1 assignment (VPC, VCC);[0052]
• (16) Hierarchy Level-2 assignment (VCC, AAL2VCC, AAL5 packet mode VCC); and[0053]
• (17) Range of VCIs available within VPC (for VPC service).[0054]
• The[0055]connection management task226, upon initialization, interfaces with theoperating system122 running on thecommunication device100 and reads the configuration information in theconnection database124 to install the user configurations (FIG. 1). If there is a VPC service to be configured, theconnection management task226 issues a request to theresource manager block222 to install a level-1 flow (and requests a QoS) for the VPC. Theresource manager block222 then establishes a level-1 flow and assigns resources to the flow. Theresource manager block222 then sends a deny or confirmation message and a Flow ID back to the connectionmanagement task block226. A deny message indicates that there are insufficient resources available if the request indicated to deny in the case of insufficient resources. A confirmation message indicates that there were either sufficient resources and a flow assigned, or insufficient resources (e.g., less than requested resources) and a flow assigned. A similar protocol is performed for VCC service. The connection management task block226 then notifies the flow classification and routing block218 of the set of VPCs and VCCs (level-1 flows) that are set up to be used by sending the Flow IDs of the VPCs and VCCs to the same.
Transmit Segment
• In the transmit segment, the forwarding[0056]API block230 passes data units, Flow IDs, and/or requests for assignment of Flow IDs and QoS from the flow classification androuting block218 to a fly-by flowadmission control block232. The fly-by flowadmission control block232 performs admission control for data unit arrivals for which there is no assigned flow. This is required due to the connectionless nature of many protocol layers (e.g., IP). For support of packet classifications, the fly-by flowadmission control block230 interacts with the flow classification androuting block218 to map protocol layer flows to level-1 or level-2 flows.
• At initialization, the[0057]connection management task226 creates pre-configured level-2 flows between the source and destination node on which it can map a layer protocol flow to the level-2 flow (e.g., mapping a new layer-3 protocol such as IP, or a layer-2 protocol such as frame relay or PPP to a level-2 flow). Each pre-configured level-2 flow is initially setup without any QoS parameters assigned to it.
• The flow classification and routing block[0058]218 passes data units and their corresponding Flow IDs to the fly-by flow admission control block232 for existing flows. The fly-by flow admission control block232 then forwards the data units to the buffer management block234 for queuing.
• To establish a new flow, the flow classification and routing block[0059]218 passes a resource request to the fly-byflow admission block232 for the QoS parameters for a new flow. QoS parameters include, but are not limited or restricted to, peak rate, sustained rate, delay, jitter, and maximum burst size. In response to the resource request, the fly-by flow block232 attempts to acquire resources for the flow by sending a request to theresource manager222. Theresource manager222 determines whether there are sufficient resources such as bandwidth, buffers, connection identifiers, delay bounded routes, etc. to meet the desired QoS associated with the flow, as indicated by the policy associated with the class. If sufficient resources exist, the fly-byflow admission block232 is notified to acquire a level-2 flow out of a pool of available level-2 flows that have not been assigned to protocol layers (e.g., layer-2 or layer-3 classified flows). The fly-byflow admission block232 then assigns to the level-2 flow, the QoS parameters requested by the flow classification androuting block218 in the SOS request. The data unit is then forwarded to the buffer management block234 for queuing. Consequently, the level-2 flow is active and able to accept and queue data units. If there are insufficient resources, the flow may be denied or accepted on an “all-others” flow (e.g., lower priority flow) as pre-determined by user configuration control.
• When flow classification and[0060]routing block218 wishes to terminate the protocol layer flow, it requests theresource manager222 to deactivate the level-2 flow. All resources that were used by the level-2 flow are returned to the resource pool and the flow is deactivated. When deactivated, the level-2 flow is no longer available to be used until it is reassigned to a new layer-3 or layer-2 flow.
• The fly-by flow[0061]admission control block232 has the advantage over explicit out-of-band flow establishment procedures such as ATM signaling or RSVP in that the data unit is not delayed by the out-of-band flow establishment process that requires communication between networking devices. Thus, with the fly-byflow admission block232, the first data unit to establish a flow is not delayed and can be immediately forwarded to the network port. This makes applications such as Voice over IP a reality in the WAN.
• Resources assigned to level-1 flows can be partitioned for purposes of limiting access. The sum of the resource partitions is equal to the resource assignment to the level-1 flow. For example, a level-1 flow may have two resource partitions, one for agency A and one for agency B (e.g., for separate LAN networks). Through flow classification, data units can be identified as being members of agency A or B. Thus, when a new data unit stream is identified, the new flow is created from the resource partition assigned to that classification type. In this way, agency A can be limited in the amount of resources that are drawn from the level-1 flow so as not to block resources from being allocated to flows belonging to agency B. Likewise, agency B has its own resource partition to draw from as not to block agency A.[0062]
• Once a flow has been established, the buffer-management block[0063]234 determines whether the queue has sufficient space for the data unit. If not, the data unit is discarded. If so, the data unit is queued in thedata unit queues236 associated with the flow. A queue is assigned to each flow. The queue operates as a FIFO and can accept packet, frames, and cells.
• Queues/buffers are allocated for each VPC, VCC, or UNI. This is used to prevent connections from depleting the buffer pool thus blocking other connections from being able to queue data for transmission. It can also be used to bound the queuing delay for a flow. A flow only uses the buffers allocated to the associated VPC, VCC, or UNI. If a flow depletes its buffer allocation, even though there are available buffers in the system, the data unit is discarded. For cases where there are a relatively large number of connections and/or interfaces, buffer allocation can be configured so that the buffers are over-allocated. This results in more buffers being available on a statistical basis with a chance that a flow might not at times be able to use its allocation. For example, 10,000 buffers are allocated to a UNI. As long as a majority of the connections are idle or have not used their entire buffer allocation, active connections can queue more packets and cells than if their buffer allocation were limited to 100 buffers.[0064]
• The[0065]queues236 are coupled to a two-tiered hierarchical shaper/scheduler block238, having a hierarchy level-1 shaper/scheduler and a hierarchy level-2 shaper/scheduler, that selects a flow for service. If the packet arrives into a non-empty queue, the flow has already been scheduled and no further action is required. That is, once a packet is queued, the flow associated with the packet is sent to the shaper/scheduler block238 for shaping and scheduling. The shaper/scheduler block238 is invoked periodically to service thequeues236. When a flow is selected for output, the associated output adaptation processing assigned to the flow is performed and the data is delivered to an output port. For example, for ATM, the output function is the ATMencapsulation layer block240 which applies the RFC1483 header to the packet. The packet is then passed to the ATMadaptation layer block242 which segments packets into cells and outputs the cells.
• FIG. 3A illustrates one embodiment of the classification technique provided in accordance with the principles of the invention, while FIG. 3B illustrates one example of Axis Preprocessing technique provided in accordance with the principles of the invention. FIG. 4 illustrates details of functional blocks within the flow classification and[0066]routing block218 according to one embodiment of the invention. With reference to FIG. 4, the flow classification androuting block218 comprises aflow classification block300, anIP forwarding block310 and aflow assignment block320 and aflow management block340. In one embodiment, the data (e.g., the tables) used for classification and searching may be stored in internal memory, e.g., indata RAM110. In alternate embodiments, the data may be stored inexternal memory120. Theflow classification block300 uses a series of searches to assign each incoming PDU to a “class.” The class assignment determines the quality of service (QoS) for a particular flow. One embodiment of the process and system for processing the flow based upon class assignments is described in co-pending application Ser. No. ______, entitled “Admission Control, Queue Management and Shaping/Scheduling for Flows,” filed concurrently herewith, and assigned to the assignee of the present invention, the contents of which are incorporated herein by reference. In one embodiment, the first search locates class information for both source and destination IP addresses. This search also locates next hop routing information for the destination address, which is passed to theIP forwarding block310. Other searches are used to locate classing information for UDP/TCP ports, protocol bye and DS/protocol byte values. The classing information from each search is added together to form a “sum of products” value which represents the PDU's class. This final value is found in a binary range tree, which returns the class descriptor. Details of the binary range tree search are described in FIGS. 5A, 5B and the accompanying text.
• The classification technique of the present invention first defines the class available for classifying each PDU. The classes may be defined in terms of: Source IP Address Ranges, Destination IP Address Ranges, DS/TOS byte ranges (Differentiated Services/Type of Service), Well known applications (destination port number for registered applications), Protocol (UDP, TCP, etc), Destination Port Number ranges or Source Port Number Ranges. It is understood that the classes may be defined by other parameters, or by a greater or lesser number of parameters. For present discussion purposes, and as shown in FIG. 3A, two classes are defined based on three parameters, RA, RB and RC. For example, parameters RA may be divided into three ranges, RA0, RA1 and RA2; parameters RB may be divided into three ranges, RB0, RB1, RB2; and parameters RC may be divided into three ranges RC0, RC1 and RC2. It is understood that each parameter may include a greater or fewer number of ranges. Each range has a plurality of values, each of which is associated with particular information and data related to the flow.[0067]
• Preprocessing begins by “projecting” each upper and lower limit value of the ranges from each class, onto an “axis. In the example shown in FIG. 3A, the upper and lower limit value of range RA0 are A1 and A0 respectively; and the upper and lower limit value of range RA1 are A2 and A1 respectively. Various points may be similarly located on each axis representing the ranges, as shown in FIG. 3A.[0068]
• Since there are three ranges, RA, RB and RC, each set of three points, one on each axis is used to create ranges, and then each range is numbered from 0 to NA (for range RA), from 0 to NB (for range RB) and from 0 to NC (for range RC), where NA, NB and NC are positive integers. The axis with the largest number of ranges becomes the least significant axis (LSA). In the present example, RC is the least significant axis, since it has 3 ranges, while RA has one range and RB has 2 ranges.[0069]
• The range number on each axis becomes the “tag” value for the axis' search process. Before saving the “tag” value into the search tree, it is first preshifted so when logically OR'ed with the “tag” values from the other searches, a unique result is formulated. The amount of the preshift depends on whether the axis is the LSA or not. If the axis is the LSA, it is not preshifted, so it's “tag” value gets placed not the least significant bits of the result, thus creating the maximum number of ranges (since the LSA is the axis with the maximum number of ranges in it). If the axis is not the LSA, it is shifted by an amount so that “2[0070]^shiftcount≧maximum number of ranges in the LSA.”
• In the example shown in FIG. 3A, the range values for[0071]Class 1 and 2 are as follows:

  Range Value onAxis	Class	1	Class 2
  RA	RA0	RA1
  RB	RB0	RB1
  RC	RC0	RC2

• Each axis' tag values are numbered in sequential order starting at 0, so the tag values associated with each range value would be:[0072]

  Axis	Class	1	Class 2
  RA	0	1 or binary 01
  RB	0	1 or binary 01
  RC	0	2 or binary 10

• Since axis RC has the most number of ranges, it becomes the LSA, and its values thus are not preshifted. The axis' are sorted by their range count values, so the order of these three axis, from least to most significant, becomes:[0073]

  RC	Least significant axis (LSA)
  RA
  RB	Most significant

• Since axis RC has 3 range/tag values, axis RA values must be preshifted by an amount equal to or greater than 3. Since this is a binary shift, the possible shift values are 1, 2, 4, 8, etc. which correspond to 2[0074]ⁿvalues where ‘n’ is the shift amount. So, axis RA's tag values would be preshifted by 2 bits (2²=4).
• Axis RB's tag values must be preshifted by an amount equal to or greater than the shift amount of axis RC, plus the total number of ranges on RA, which is 2[0075]²+2=6. So, axis RB's tag values would be shifted by 3 bits (2³=8).
• So, the resulting preshifted values would be:[0076]

  	Axis	Class	1	Class 2
  	RA	0	4 or binary 100
  	RB	0	8 or binary 1000
  	RC	0	2 or binary 10

• Now, suppose a PDU is received which has values which fall into the following ranges:[0077]
• [0078]value 1 from PDU is within range RA0.
• [0079]value 2 from PDU is within range RB1.
• value 3 from PDU is within range RC2.[0080]
• The preshifted tag values for each of these are then OR'ed together:[0081]
• 0 OR 8 OR 2=10[0082]
• The value 10 is then found in the Final Classification Binary Range Tree which yields the “class” designation for the PDU, which in the case of FIG. 3A, would be[0083]class 2.
• The preshifted values are stored in the corresponding nodes of a Binary Range Tree (see FIGS. 5A, 5B and accompanying text), so when a value is found within the range, the range's preshifted “tag” value is located. Since the values are preshifted, the only additional processing required is to OR them together to form a final “tag” value. This final “tag” value is finally found in a Binary Range Tree which results in the actual “class” for the PDU.[0084]
• FIG. 3B illustrates a simple example of the classification system provided in accordance with the principles of the invention. In this example, the classification system is based only on source and destination IP addresses. As shown in FIG. 3B, three classes are defined as follows:[0085]
• [0086]Class 1=Any PDU from IP addresses 192.1.1.1 to 2.1.5.255, and destined for any IP address in the range 192.1.1.1 to 255.255.255.255.
• Class=Any PDU from IP addresses 192.1.1.1 to 200.1.5.255, and destined for any IP address in the range 200.1.5.1 to 200.1.5.255.[0087]
• Class 3=Any PDU from IP addresses 192.1.1.1 to 192.1.1.255, and destined for any IP address in the range 192.1.1.1 to 192.1.1.255.[0088]
• Preprocessing begins by “projecting” each upper and lower limit value, from each class, onto an imaginary “axis,” as illustrated at the top of FIG. 3B. For the 3 class definitions, this results in the following “points” on each “axis.”[0089]
• On the “Source IP Axis:”[0090]
• [0091]Point 1=0.0.0.0 (this is always assumed to be there)
• [0092]Point 2=192.1.1.1 (lower value from all 3 classes)
• Point 3=192.1.1.255 (upper value from class 3)[0093]
• Point 4=200.1.5.255 (upper value from all three classes)[0094]
• Point 5=255.255.255.255 (this is always assumed to be there)[0095]
• On the “Destination IP Axis:”[0096]
• [0097]Point 1=0.0.0.0 (this is always assumed to be there)
• [0098]Point 2=192.1.1.1 (lower value fromclasses 1 & 3)
• Point 3=192.1.1.255 (upper value from class 3)[0099]
• Point 4=200.1.5.1 (lower value from class 2)[0100]
• Point 4=200.1.5.255 (upper value from class 2)[0101]
• Point 5=255.255.255.255 (upper value from class 1)[0102]
• Each set of two points on each axis is used to create ranges, and then each range is numbered[0103]form 0 to n. The following ranges are produced from the above example:
• On the “Source IP Axis:”[0104]
• [0105]Range 0=0.0.0.0 to 192.1.1.0
• [0106]Range 1=192.1.1.1 to 192.1.1.255
• [0107]Range 2=192.1.2.0 to 200.1.5.255
• Range 3=200.1.6.0 to 255.255.255.255[0108]
• On the “Destination IP Axis:”[0109]
• [0110]Range 0=0.0.0.0 to 192.1.1.0
• [0111]Range 1=192.1.1.1 to 192.1.1.255
• [0112]Range 2=192.1.2.0. to 200.1.5.0
• Range 3=200.1.5.1. to 200.1.5.255[0113]
• Range 4=200.1.6.0 to 255.255.255.255[0114]
• The axis with the largest number of ranges becomes the least significant axis (LSA). In this example, the LSA would be the “Destination IP Axis” since it has 5 ranges compared to only 4 on the “Source DP Axis.”[0115]
• The range number on each axis become the “tag” value for the axis' search algorithm. Before saving the “tag” value into the search tree, it is first preshifted so when logically ORed with the “tag” values from the other searches, a unique result is formulated. The amount of the preshift depends on whether the axis is the LSA or not. If the axis is the LSA, it is not preshifted, so it's “tag” value gets placed not the least significant bits of the result, thus creating the maximum number of ranges (since the LSA is the axis with the maximum number of ranges in it). If the axis is not the LSA, it is shifted by an amount so that “2[0116]^shiftcount≧maximum number of ranges in the LSA.” Since the LSA in this example has 5 ranges, the other axis' “tag” values are shift by 3 bits (2³=8 which is greater than 5 ranges in the LSA).
• In particular, each axis' tag values (except for the LSA) are shifted by an amount equal to the maximum number of bits required to represent the maximum tag value for each axis which has lower significance than the axis in question. In the above example, the LSA (the Destination IP Address Axis) has a maximum tag value of 4 (where 0, 1, 2, 3, 4 are the values of each tag). A “4” requires 3 bits to encode (binary 100=decimal 4). As a result, each tag value for the non-LSA (the Source IP Address Axis) is shifted left by 3 bits. This is the same as multiplying each tag value by 2[0117]³=8.
• The preshifted values are stored in the corresponding nodes of the Binary Range Tree, so when a value is found within the range, the range's preshifted “tag” value is located. Since the values are preshifted, the only additional processing required is to OR them together to form a final “tag” value. This final “tag” value is finally found in a Binary Range Tree which results in the actual “class” for the PDU. Thus, in the present example, Source[0118]IP tag values 0, 1, 2 and 3 become 0, 8, 16 and 24 respectively, which are then stored in the classification tables.
• If a PDU is classified so that its Source IP address matches Class 3, the value read from the Source IP table would be 8 (tag value of 1 shifted by 3 bits). If the same PDU's Destination IP address matches[0119]class 2, the value read from the Destination IP table would be 3 (tag value is 3, which is not shifted because the destination axis is the LSA). These two values are combined to form 8+3=11. The value 11 is then found in the final classification binary range tree.
• With reference to FIG. 4, the[0120]IP forwarding block310 uses the next hop information resulting from the PDU's classification to rout the PDU. The routed PDU, along with the class definition, LIP list and network address information, is passed to theflow assignment block320.
• The[0121]flow assignment block320 utilizes the class descriptor found by theflow classification block300 to locate the outbound flow ID for a PDU. The PDU is provided to the forwardingAPI block230 in the Queue Control/Transmit (QCT)module205, along with its flow ID, LIF list and class definition information. If the flow ID is valid theQCT module205 queues the PDU and returns a “successful” indication. If the flow ID was either invalid (dropped by the QCT module205) or nonexistent (i.e., it is a new flow), theQCT module205 will attempt to assign a flow ID. If successful, the new flow ID is returned is returned to the flow assignment block, which then saves the information in the original class descriptor. If a flow ID could not be assigned, theQCT module205 retries transmission using the “all others” class.
• The[0122]flow management block330 generates and updates a set of tables (indexed by protocol, DS byte and port values) to be used by theflow classification block300. In one embodiment, the set of tables include a class definition table332, a policy definition table, and a pipe definition table336. The tables332,334 and336 facilitate efficient assignment of an incoming PDU to a “class”. The tables332,334 and336 also assign a class descriptor value to each PDU, which is passed in the buffer descriptor. Theflow management block340 also createsclass descriptors340 to be used by theflow assignment block320. Theclass descriptors340 are referenced by the classification tables304. Theflow assignment block330 uses theclass descriptors340 to locate an outbound flow ID for a PDU.
• The[0123]QCT module205 sends “events” such as bandwidth changes, to theflow management block330. These events may cause theclass descriptors340 to be rebuilt due to changes in policies, as described in detail in the following sections. Theflow management block330 also handles traffic management requests.
• More particularly, the[0124]flow classification block300 processes up to a predetermined number of PDUs in parallel, assigning each to a class. For discussion purposes, the predetermined number of PDUs is 4, although it is understood that a greater or lesser number of PDUs may be processed in parallel in accordance with the principles of the present invention. The flow classification block also obtains the destination routing information, which is saved in a buffer descriptor (where?) for later use by theIP forwarding block310. If theflow classification block300 determines that a PDU must be discarded, it is marked in the buffer descriptor. Theflow assignment block320 will subsequently discard the PDU. The resulting class information is stored in the buffer descriptor, which the flow assignment block uses to assign the PDU to a specific flow.
• Each type of traffic to be identified by the[0125]flow classification block300 must be defined by a class definition. A class definition will allow a system administrator to specify the IP address range, protocol values, DS byte values and UDP/TCP port values to be identified in forwarded IP PDUs, which then becomes part of the class. In one embodiment, there are 1024 different classes. One or more of the following criteria can be combined to form a template for the PDUs associated with a class:
• Source IP Address Ranges[0126]
• Destination IP Address Range[0127]
• DS/TOS byte range (Differentiated Services/Type of Service[0128]
• Well known application (destination port number for registered applications)[0129]
• Protocol (UDP, TCP, etc)[0130]
• Source Port Number Range[0131]
• Destination Port Number Range[0132]
• By default, an “all others” class is defined which will match any incoming PDU and use a “best effort” policy for delivery. User defined classes will essentially be included in the “all others” class.[0133]
• The class definition table[0134]332 allows a class of IP PDUs to be defined. Table 1 (See Appendix) illustrates one example of the table objects and their usage. In one embodiment, the table is instanced by the ClassDefinitionIndex.
• The policy definition table[0135]334 associates a class definition with a pipe definition. In one embodiment, there are 2048 different policies. One or more of the following criteria can be combined to form a policy which will associate a pipe definition with a class definition:
• Outgoing priority value for queuing[0136]
• Outgoing DS byte value[0137]
• Bandwidth allowed for each flow within the class[0138]
• Discard priority[0139]
• Table 2 (See Appendix) illustrates an example of the Policy Definition Table, which is instanced by PolicyDefinitionIndex.[0140]
• The pipe definition table[0141]336 creates a slice of the available circuit's bandwidth (e.g., in the case of ATM, the VCC), which can be mapped to classes of incoming data. A single pipe definition causes a single flow aggregate to be created within QCT module's205'slevel 2 scheduler. In one embodiment, there are 1024 different pipe definitions. The following criteria is defined for each pipe:
• Logical interface[0142]
• WAN circuit identifier (or 0 for a LAN interface)[0143]
• Percentage of bandwidth to assign to the pipe[0144]
• Maximum queuing delay allowed on pipe.[0145]
• Table 3 (See Appendix) illustrates one embodiment of the pipe definition table[0146]336. The table is instanced by PipeDefinitionIndex.
• To classify PDUs, several searches are performed. The first search utilities a Routing Table[0147]302 to locate classing information based on source and destination IP addresses. In one embodiment, the search engine for this search is based on the Binary Range Tree search process of the present invention, as discussed in detail in the following sections. In one embodiment, the routing table302 stores routing information. In an alternate embodiment, the routing table302 stores both routing and classing information. In one embodiment, the routing table302 is shared between the flow classification and IP forwarding blocks300 and320.
• The other searches locate classing information based on UDP/TCP ports, DS and protocol bytes. In one embodiment, these engines utilize an “array look-up” search technique, as known by one of skill in the art, to conduct the other searches. The flow classification tables[0148]304 are used by the “array look-up” search technique to locate classing information based on UDP/TCP ports and DS/protocol bytes.
• The PDUs classified by the[0149]flow classification block300 are forwarded, along with their associated routing information, to theIP forwarding block310. TheIP forwarding block310 identifies an outbound LIF for each received PDU and then passes this information to theflow assignment block320. The PDUs are then forwarded to theQCT module205. As described earlier, if theflow assignment block320 determines that a PDU must be discarded, it is marked in the buffer descriptor. Theflow assignment block320 will subsequently discard the PDU thus marked.
• FIG. 5A illustrates one embodiment of a search process flow provided in accordance with the principles of the present invention. The[0150]search process flow500 facilitates searching of data corresponding to various parameter ranges of incoming PDUs. An example of the ranges to be searched includes the IP Address of the incoming PDUs. The data associated with the IP address ranges are stored within the CPU's105's internal memory, such as in cache memory. Data outside of the IP address ranges may be stored inSRAM120 or other in other memory locations external to the CPU105.
• The search process involves determining if the value k associated with the incoming PDU is located in any one of the stored ranges located in the CPU's[0151]105's internal memory. If so, data associated with the stored ranges may be efficiently retrieved. Each set of stored ranges is located in a node of a tree, with the search progressing from a root or upper level node to a secondary or lower level nodes. Thesearch process flow500 operates as follows. Beginning from a start state, theprocess500 proceeds to decision block502, where it determines if the node is null (i.e., contains no data). If so, theprocess500 proceeds to process block504, where it returns a default result. In one embodiment, the default result is to assign the PDU having the value k to an “all others class”. In this case, best efforts will be used to transport the corresponding PDU. If the node is not null, theprocess500 proceeds to read the node's range, as shown inprocess block506. Theprocess500 then advances to process block508, where it queries if k is less than the node's range. If so, theprocess500 proceeds to process block510, where it selects to proceed to a node having a range that is less than the current node. Theprocess500 then returns todecision block504. Otherwise, theprocess500 proceeds to decision block512, where it determines if k is greater than the node's range. If so, theprocess500 proceeds to process block514, where it selects to proceed to a node having a range that is greater than the current node. Theprocess500 then proceeds todecision block504. Otherwise, theprocess500 proceeds to process block516, where it returns the result from the node in which k is found. For example, data associated with k, as found within the node, is returned. Theprocess500 is then terminated.
• FIG. 5B is a diagram that illustrates one example of the search process of FIG. 5A. In this example, the value k (such as the IP address ranges) and the corresponding data are stored in internal memory of CPU[0152]105. These IP address ranges include range 192.1.1.1-192.1.1.255, 193.1.1.1-193.1.1.255, 200.255.1.1-200.255.255.255, 191.1.0.1-191.1.0.255, 192.1.0.1-192.1.0.255 and 163.1.1.1-163.1.1.255. Theprocess550 begins the search by determining if the IP address of the incoming PDU is located in range 192.1.1.1-192.1.1.255 (block552). If so, the data corresponding to the IP address located in range 192.1.1.1-192.1.1.255 is retrieved. Otherwise, theprocess550 proceeds to search in ranges that are both greater than and less than range 192.1.1.1-192.1.1.255.
• For example, the[0153]process550 may proceed to search in the range 193.1.1.1-193.1.1.255 (block554). If the IP address is found to be in that range, the corresponding data is retrieved. Otherwise, theprocess550 proceeds to search in the range 200.255.255.255. If the IP address is found in the range 200.255.255.255, the corresponding data is retrieved. Otherwise, a default search result is returned.
• The[0154]process550 may also proceed to search in the range 191.1.0.1-191.1.0.255 (block558). If the IP address is found to be in that range, the corresponding data is retrieved. Otherwise, theprocess550 proceeds to search in ranges that are both greater than or less than that of range 191.1.0.1-191.1.0.255. For instance, theprocess550 may search in the range 192.1.0.1-192.1.0.255. If the IP address is found to be in that range, the corresponding data is retrieved. Otherwise, theprocess550 returns a default search result. Theprocess550 may also search in the range 163.1.1.1-163.1.1.255. Similarly, if the IP address is found to be in that range, the corresponding data is retrieved. Otherwise, theprocess550 returns a default search result.
• In the example of FIG. 5B, a binary range search tree that is 3 levels deep is discussed. It is understood that any number of levels that are greater or less than that may be implemented for searching purposes. It has been determined that binary range searches of up to 6 levels may be implemented and stored in the internal memory of a processor such as cache memory, while providing efficient searching. This aspect of the invention thus facilitates efficient searching and identification of incoming data while maintaining the worst case and average case search times deterministic and within the bounds required by the application.[0155]
• The present invention thus provides a classification system and method by implementing Axis Preprocessing in combination with a Binary Range Tree searching technique. The Binary Range Tree searching technique allows large ranges of contiguous values to be search using a minimal number of tree “nodes”, while the Axis Preprocessing technique assures that the maximum number of contiguous ranges is generated in the final “class” search step.[0156]
• While certain exemplary embodiments have been described and shown in the accompanying drawings, it is to be understood that such embodiments are merely illustrative of and not restrictive on the broad invention, and that this invention not be limited to the specific constructions and arrangements shown and described, since various other modifications may occur to those ordinarily skilled in the art.[0157]

  TABLE 1
  Object	Type	Permissions	Description
  ClassDefinitionIndex	Unsigned	Read Only	The index value for this Class Definition (1-
  	Long		1024)
  ClassDeflnitionAlias	Octet	Read/Write	An alias to assign to this class
  	String
  ClassDefinitionParentClassID	Unsigned	Read/Write	Parent class definition if using a hierarchy of
  	Long		classes.
  ClassDefinitionFlowType	Enum	Read/Write	The type of flow . . . NORMAL, CHANNELED,
  			DIFFSERVINGRESS, DIFFSERVNODE,
  			DIFFSERVEGRESS, or DELETE. Set to
  			DELETE to remove this Class Definition from
  			the table.
  ClassDefinitionSourceIPMask	IP address	Read/Write	The value to mask each source IP address with
  			before checking its range. (not valid for
  			DIFFSERVNODE or DIFFSERVEGRESS
  			types)
  ClassDefinitionDestIPMask	IP address	Read/Write	The value to mask each destination IP address
  			with before checking its range . . . (not valid for
  			DIFFSERVNODE or DIFFSERVEGRESS
  			types)
  ClassDefinitionSourceIPLower	IP address	Read/Write	The first source IP which is within the range . . .
  Bound			(not valid for DIFFSERVNODE or
  			DIFFSERVEGRESS types)
  ClassDefinitionSourceIPUpper	IP address	Read/Write	The last source IP which is within the range . . .
  Bound			(not valid for DIFFSERVNODE or
  			DIFFSERVEGRESS types)
  ClassDefinitionDestIPLower	IP address	Read/Write	The first destination IP which is within the
  Bound			range . . . (not valid for DIFFSERVNODE or
  			DIFFSERVEGRESS types)
  ClassDefinitionDestIPUpper	IP address	Read/Write	The last destination IP which is within the range . . .
  Bound			(not valid for DIFFSERVNODE or
  			DIFFSERVEGRESS types)
  ClassDefinitionDSLowerBound	Unsigned	Read/Write	The first DS/TOS byte value which is within
  	Byte	range.
  ClassDefinitionDSUpperBound	Unsigned	Read/Write	The last DS/TOS byte value which is within
  	Byte		range. (not valid for DIFFSERVNODE or
  			DIFFSERVEGRESS types)
  ClassDefinitionWellKnownAppli	Enum	Read/Write	The “well known application” value (see 4.1.1),
  cation			or 0×ff if not used . . . (not valid for
  			DIFFSERVNODE or DIFFSERVEGRESS
  			types)
  ClassDefinitionProtocol	Enum	Read/Write	(Valid if ClassDefinitionWellKnownApplication
  			is not used) . . . TCP, UDP, TCPUDP, rfc 1700
  			defined protocols. or ANY . . . (not valid or
  			DIFFSERVNODE or DIFFSERVEGRESS
  			types)
  ClassDefinitionSourcePortLower	Unsigned	Read/Write	(Valid if ClassDefinitionWellKnownApplication
  Bound	Short		is not used) . . . The first source port value which
  			is within range . . . (not valid for
  			DIFFSERVNODE or D1FFSERVEGRESS
  			types)
  ClassDefinitionSourcePortUpper	Unsigned	Read/Write	(Valid if ClassDefinitionWellKnownApplication
  Bound	Short		is not used) . . . The last source port value which
  			is within range . . . (not valid for
  			DIFFSERVNODE or DIFFSERVEGRESS
  			types)
  ClassDefinitionDestPortLower	Unsigned	Read/Write	(Valid if ClassDefinitionWellKnownApplication
  Bound	Short		is not used) . . . The first destination port value
  			which is within range . . . (not valid for
  			DIFFSERVNODE or DIFFSERVEGRESS
  			types)
  ClassDefinitionDestPortUpper	Unsigned	Read/Write	(Valid if ClassDefinitionWellKnownApplication
  Bound	Short		is not used) . . . The last destination port value
  			which is within range . . . (not valid for
  			DIFFSERVNODE or DIFFSERVEGRESS
  			types)
  ClassDefinitionSLAMonitorRate	Unsigned	Read/Write	The interval (in seconds) between SLA
  	Short		monitoring. A value of 0 disables SLA
  			monitoring for this class.
  ClassDefinitionSLAAlarmRate	Unsigned	Read/Write	The minimum interval (in seconds) between
  	Long		SLA alarms.
  ClassDefinitionSLAAlarmThresh	Unsigned	Read/Write	The number of alarm conditions which must
  old	Long		occur before an actual alarm is generated.
  ClassDefinitionLIFAgingTime	Unsigned	Read/Write	The number of milliseconds to use as an aging
  	Long		time for Flow ID information saved for a LIF.
  			This aging time is also used for classification
  			information which is automatically created for a
  			channelized flow.

• [0158]

  TABLE 2
  Object	Type	Permissions	Description
  PolicyDefinitionIndex	Unsigned	Read Only	The index value for this Policy Definition (1-
  	Long		1024).
  PolicyDefinitionAlias	Octet	Read/Write	An alias to assign to this policy
  	String
  PolicyDefinitionType	Enum	Read/Write	NORMAL. DIFFSERVINGRESS.
  			DIFFSERVNODE, DIFFSERVEGRESS,
  			DISCARD, or DELETE. Set to DELETE to
  			remove this Policy Definition.
  PolicyDefinitionLIF	Unsigned	Read Only	The logical interface this relates to.
  PolicyDefinitionStartTime	Time of	Read/Write	The time this policy comes into effect.
  	Day
  PolicyDefinitionEndTime	Time of	Read/Write	The time this policy goes out of effect.
  	Day
  PolicyDefinitionDayof Week	Unsigned	Read/Write	Bit flags corresponding to each day of the
  	Byte		week . . . (Bits 0-6 = Monday-Sunday).
  PolicyDefinitionPipeID	Unsigned	Read/Write	The Pipe to associate with this Policy.
  	Long
  PolicyDefinitionClassID	Unsigned	Read/Write	The Class to associate with this Policy.
  	Byte
  PolicyDefinitionChannelBandwidth	Unsigned	Read/Write	The bandwidth allowed for each flow over this
  	Long		Class/Policy. Only valid is
  			PolicyDefinitionChannelized is set TRUE.
  PolicyDefinitionChannelized	Boolean	Read/Write	Set TRUE if this Policy defines channelized
  			flows over the specified Pipe. This causes each
  			new flow to be given a unique “slice” of the
  			available bandwidth, as defined by
  			PolicyDefinitionChannelBandwidth. If FALSE,
  			then all flows use the Pipe's bandwidth on a
  			first-come-first-served basis.
  PolicyDefinitionOutboundDSValue	Unsigned	Read/Write	The DS byte value to set in outbound PDUs, or
  	byte		NA if no replacement is to be performed. (valid
  			only is set to DIFFSERV).
  PolicyDefinitionPriority	Unsigned	Read/Write	The relative priority of PDUs using this Policy
  	byte		with respect to other Policies.
  PolicyDefinitionEvent	Enum	Read/Write	STATIC - the Policy is always in effect unless
  			superceded by another. The Policy becomes the
  			default. TIME - the Policy goes into effect and
  			goes out of effect based on the Time and Day
  			values specified. REDUCEDBW - the Policy
  			goes into effect if the Pipe's bandwidth is
  			reduced by the physical interface.
  			INCREASEDBW - the Policy goes into effect if
  			the Pipe's bandwidth is increased by the
  			physical interface.

• [0159]

  TABLE 3
  Object	Type	Permissions	Description
  PipeDefinitionIndex	Unsigned	Read Only	The index value for this Pipe Definition (1-
  	Long		1024).
  PipeDefinitionType	Enum	Read/Write	VALID - the Pipe is valid. DELETE - to
  			remove the Pipe Definition.
  PipeDefinitionAlias	Octet	Read/Write	An alias to assign to this Pipe.
  	String
  PipeDefinitionLIF	Unsigned	Read/Write	The logical interface this Pipe is using.
  	Long
  PipeDefinitionCircuitID	Unsigned	Read/Write	The ID of the circuit this Pipe is using.
  	Long
  PipeDefinitionBandwidth	Unsigned	Read/Write	The amount of the circuit's bandwidth to assign
  	Long		to this Pipe. If the value is <=100, it is
  			considered to be a “percentage” value. If the
  			value is >100. it is considered to be a “bits per
  			sec”value.
  PipeDefinitionDelay	Unsigned	Read/Write	The maximum allowable queuing delay for this
  	Long		Pipe.

Claims (21)

What is claimed is:

1. A method for classifying information received by a communications device, comprising:

(a) defining a first parameter having a first parameter range and a second parameter range, and a second parameter having a third parameter range and a fourth parameter range;

(b) defining a first class having one of said first parameter and said second parameter ranges, and one of said third and said fourth parameter ranges;

(c) defining a second class having another one of said first parameter and said second parameter ranges, and another one of said third and said fourth parameter ranges;

(d) receiving information having a first parameter value and a second parameter value;

(e) determining if said first parameter value is within one of said first and second parameter ranges and determining if said second parameter value is within one of said third and fourth parameter ranges, if so, classifying said information into one of said first and second classes based on said first parameter value and said second parameter value, otherwise classifying said information as a default class; and

(f) generating an output value representative of said classification.

2. The method ofclaim 1, wherein the first and the second parameter ranges are the same.

3. The method ofclaim 1, wherein the third and fourth parameter ranges are the same.

4. The method ofclaim 1, further comprising:

providing a predetermined quality of service for processing said information based on said classification.

5. The method ofclaim 1, further comprising, prior to (d):

(c.1) allocating a value to each of said first, second, third and fourth parameter ranges;

(c.2) determining a least significant parameter based on the number of parameter ranges;

(c.3) shifting the values of each of said first, second, third and fourth parameter ranges that are not determined to be associated with said least significant parameter, by a predetermined amount;

(c.4) adding said values of said first and second parameter ranges to provide a first output value, and adding said values of said second and third parameter ranges to provide a second output value;

(c.5) providing said first output value as a first class tag value and said second output value as a second class tag value.

6. The method ofclaim 4, wherein (e) further comprises:

assigning a class tag value to the received information.

7. The method ofclaim 5, further comprising:

providing a predetermined quality of service for processing the information based on said class tag value.

8. A computer program product comprising:

a computer usable medium having computer program code embodied therein for searching for information in a processing unit, the computer program product having:

(a) computer readable program code for defining a first parameter having a first parameter range and a second parameter range, and a second parameter having a third parameter range and a fourth parameter range, for defining a first class having one of said first parameter and said second parameter ranges, and one of said third and said fourth parameter ranges, and for defining a second class having another one of said first parameter and said second parameter ranges, and another one of said third and said fourth parameter ranges;

(b) computer readable program code for receiving information having a first parameter value and a second parameter value;

(c) computer readable program code for determining if said first parameter value is within one of said first and second parameter ranges and determining if said second parameter value is within one of said third and fourth parameter ranges, if so, classifying said information into one of said first and second classes based on said first parameter value and said second parameter value, otherwise classifying said information as a default class; and

(d) computer readable program code for generating an output value representative of said classification.

9. The computer program product ofclaim 8, wherein the first and the second parameter ranges are the same.

10. The computer program product ofclaim 8, wherein the third and the fourth parameter ranges are the same.

11. The computer program product ofclaim 8, wherein said computer readable code further for providing a predetermined quality of service for processing said information based on said classification.

12. The computer program product ofclaim 8, wherein said computer readable code further for

(a.1) allocating a value to each of said first, second, third and fourth parameter ranges;

(a.2) determining a least significant parameter based on the number of parameter ranges;

(a.3) shifting the values of each of said first, second, third and fourth parameter ranges that are not determined to be associated with said least significant parameter, by a predetermined amount;

(a.4) adding said values of said first and second parameter ranges to provide a first output value, and adding said values of said second and-third parameter ranges to provide a second output value;

(a.5) providing said first output value as a first class tag value and said second output value as a second class tag value.

13. The computer program product ofclaim 11, wherein said computer program product further for assigning a class tag value to the received information.

14. The computer program product ofclaim 13, wherein said computer program product further for providing a predetermined quality of service for processing the information based on said class tag value.

15. A system comprising:

a processor having a processing unit;

a memory module coupled to said processor, said memory module having instruction sequences to cause said processor to:

(a) define a first parameter having a first parameter range and a second parameter range, and a second parameter having a third parameter range and a fourth parameter range;

(b) define a first class having one of said first parameter and said second parameter ranges, and one of said third and said fourth parameter ranges;

(c) define a second class having another one of said first parameter and said second parameter ranges, and another one of said third and said fourth parameter ranges;

(d) receive information having a first parameter value and a second parameter value;

(g) determine if said first parameter value is within one of said first and second parameter ranges and determining if said second parameter value is within one of said third and fourth parameter ranges, if so, classifying said information into one of said first and second classes based on said first parameter value and said second parameter value, otherwise classifying said information as a default class; and

(h) generate an output value representative of said classification.

16. The system ofclaim 15, wherein the first and the second parameter ranges are the same.

17. The system ofclaim 15, wherein the third and the fourth parameter ranges are the same.

18. The system ofclaim 15, wherein said instruction sequences further cause said processor to provide a predetermined quality of service for processing said information based on said classification.

19. The system ofclaim 15, wherein said instruction sequences further cause said processor to, prior to act (d):

(c.1) allocating a value to each of said first, second, third and fourth parameter ranges;

(c.2) determining a least significant parameter based on the number of parameter ranges;

(c.3) shifting the values of each of said first, second, third and fourth parameter ranges that are not determined to be associated with said least significant parameter, by a predetermined amount;

(c.4) adding said values of said first and second parameter ranges to provide a first output value, and adding said values of said second and third parameter ranges to provide a second output value;

(c.5) providing said first output value as a first class tag value and said second output value as a second class tag value.

20. The system ofclaim 19, wherein (e) further comprises:

assigning a class tag value to the received information.

21. The system ofclaim 20, wherein the instruction sequences further cause said processor to provide a predetermined quality of service for processing the information based on said class tag value.

Images