Distributed computation in network devices

The present invention facilitates routing traffic over a network and distributing application level support among multiple routing devices during routing. Routing nodes are configured to process the content of the traffic to provide the requisite application level support. The traffic is routed, in part, based on the resources available for providing the processing. The processing of the traffic may be distributed throughout the network based on processing capacity of the routing nodes at any given time and given the amount of network congestion.

FIELD OF THE INVENTION

The present invention relates to processing and routing packets in a network, and in particular, to distributing application level processing among one or more routing devices during high-speed routing.

BACKGROUND OF THE INVENTION

Existing routers have limited computation capacity and offer little or no application layer support during routing. These routers are typically divided into a control plane and a forward plane. The control plane is used for basic setup and control of the router. For example, the control plane is generally used to establish routing tables used by the forward plane. The forward plane receives packets, processes the packets based on the routing tables set up by the control plane, and delivers the packets to the next-hop address or the final destination, depending on the termination point for each packet.

The forward plane in existing routers is typically limited to packet delivery based on basic header analysis and manipulation. Historically, application layer support, such as that requiring analysis or manipulation of the packet's payload, has been avoided. Those specially configured devices capable of providing application processing, such as firewalls, are uniquely configured for the special application wherein the routing speeds for normal routing in the forward plane are significantly impacted or the control plane is uniquely adapted to handle such processing. In either case, basic routing capability of the forward plane is inhibited. Thus, traditional network routers typically do not provide application level processing, and routing devices providing such support are only used in limited applications.

Nortel Networks Limited is developing routing devices capable of providing application level processing without significantly impacting forwarding performance for the packets being processed at an application level or for those requiring only basic routing. These routing devices are capable of providing various types of application level support to facilitate any number of functions or network services.

Although these routing devices provide application level support during routing, for any given traffic flow, a single device may not have the computational capacity to provide all of the processing for a given traffic flow. The capacity may be limited based on the routing device's capability or the processing required for concurrent traffic flows. Further, congested networks incorporating routing devices capable of providing application level support would be more efficient if processing could be distributed to less congested devices, which are comparably capable.

Thus, there is a need to distribute processing for application level support among routing devices capable of providing such support. There is a further need to be able to detect congested routing devices and direct traffic to routing devices with capacity for application level support without significantly impacting routing efficiency and speeds.

SUMMARY OF THE INVENTION

The present invention facilitates routing traffic over a network and distributing application level support among multiple routing devices during routing. Routing nodes are configured to process the content of the traffic to provide the requisite application level support. The traffic is routed, in part, based on the resources available for providing the processing. The processing of the traffic may be distributed throughout the network based on processing capacity of the routing nodes at any given time and given the amount of network congestion.

When traffic is routed, processing resources required for delivery of the traffic from a source to the destination are determined. Since multiple routing paths may exist, one or more paths between the source and destination capable of providing the requisite application level support during routing are identified. Next, the available processing resources in the possible paths are compared with the resources required for routing. One or more paths are then selected to optimize routing and minimize congestion. Upon selection of the one or more paths, the traffic may be routed and processed accordingly.

The requisite application level processing may be distributed among multiple routing nodes and paths to make sure that sufficient resources are available and delivery does not negatively affect other traffic. The distribution of the processing is preferably based on available resources and perhaps on other network conditions bearing on the processing and routing performance for the particular traffic flow, the network in general, or a combination thereof.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

The present invention provides for distributing application level support among multiple routing devices during routing. The application layer support may include any type of processing or network service on packet content. The embodiments set forth below represent the necessary information to enable those skilled in the art to practice the invention and illustrate the best mode of practicing the invention. Upon reading the following description in light of the accompanying drawing figures, those skilled in the art will understand the concepts of the invention and will recognize applications of these concepts not particularly addressed herein. It should be understood that these concepts and applications fall within the scope of this disclosure and the accompanying claims.

With reference toFIG. 1A, a network2is illustrated providing for communications between an application server4and a computing device6, such as a personal computer. A communication server8may be provided to facilitate distribution of application level support among routing nodes10that are capable of providing the application level support while routing traffic between the application server4and the computing device6. As will be discussed in greater detail below, the routing nodes10are capable of providing high-speed routing services in conjunction with processing content carried in the packets between the application server4and the computing device6during routing.

The routing nodes10may take on any type of configuration capable of providing application level support on packet content during routing. However, the preferred embodiment of the invention provides for configuring the routing nodes10to include three primary processing planes: a control plane12, a compute plane14, and a forward plane16. Preferably, all incoming packets are received by the forward plane16through various ports interacting with a network, such as a packet-switched network. The forward plane16is configured to analyze each of the incoming packets and determine where to send each packet. In general, the incoming packets need to be forwarded on toward their final destination, to the control plane12, or to the compute plane14.

Preferably, any packet processing provided by the forward plane16is limited to manipulating information in one or more headers of the packet as necessary in traditional routing. Packets entering the forward plane16that require application level processing, which may entail manipulation of the packet's payload, are directed to the compute plane14by the forward plane16. After processing, the packets are returned to the forward plane16for further processing. Additional details of the configuration of the preferred routing node are outlined after a discussion of the concepts of the present invention.

An exemplary traffic flow between the application server4and a computing device6is shown inFIG. 1B. The routing nodes10are illustrated to depict the control plane12, compute plane14, and forward plane16. In the present example, assume that the media flow is routed between the application server4and the computing device6through routing nodes10A,10B and10C. Further assume that each of the routing nodes10A,10B and10C will provide application level processing on all or select packets constituting the traffic flow. The traffic flow is illustrated by the solid line extending into the compute planes14through the forward planes16of each of the routing nodes10A,10B and10C.

With the traffic flow depicted inFIG. 1B, application level processing provided by the routing nodes10A,10B and10C may be distributed in a number of ways. For example, each of the routing nodes10A,10B and10C may provide the same type of processing wherein each of the routing nodes10A,10B and10C provides processing for a certain portion of the traffic flow. As such, each of the routing nodes10A,10B and10C may process one third of the traffic or routing node10A may provide 80 percent of the processing wherein routing nodes10B and10C each provide 10 percent of the processing. Alternatively, each of the routing nodes10A,10B and10C may provide a different type of processing on the entire traffic flow. For example, routing node10A may provide a compression application, routing node10B may provide an encryption function and routing node10C may provide an e-commerce related application on the compressed and encrypted traffic flow. Alternatively, a network device or server along the way will be able to do all the computation.

Actual distribution of the application layer support for the traffic flow may be facilitated by the communication server8or by a protocol implemented between the routing nodes10and perhaps the application server4or personal computer6. If the communication server8is used to distribute processing throughout the network2among the compatible routing nodes10, information is collected from each of the routing nodes10continuously or on a periodic basis to determine the resources available or the remaining processing capacity of the various routing nodes.

An alternative traffic flow is depicted inFIG. 10wherein the traffic flow is routed from the application server4to the personal computer6via routing devices10A,10D, and10C. Notably, routing nodes10A and10C simply forward traffic while the routing node10D provides application level processing. The solid line representing the traffic flow extends into the compute plane14of routing node10D, whereas the traffic flow is solely handled by the forward plane16in routing nodes10A and10C. The traffic flow may be configured in such a manner because routing nodes10A and10C are currently processing other traffic to an extent that they lack sufficient capacity to handle all or any portion of the processing required for the traffic flow depicted. Alternatively, routing nodes10A and10C may not be configured to provide the same type of processing as that provided in routing node10D.

FIG. 1Ddepicts three different traffic flows between the application server4and the computing device6. The flows are represented by a solid line, a dotted line, and a dashed line. The traffic flow represented by the solid line is depicted as extending into the compute planes14of each of routing nodes10A,10D, and10C. As such, processing for application level support is distributed for that traffic flow between each of the three routing nodes10A,10D, and10C. The traffic flows represented by the dotted and dashed lines are routed through routing nodes10A,10B, and10C, respectively. For the traffic flow represented by the dotted line, application level support is only provided by routing nodes10B and10C, wherein routing node10A operates to simply forward packets between the application server4and routing node10B. The traffic flow represented by the dashed line receives application level processing by routing nodes10A and10B, wherein routing node10C merely forwards the packets between10B and the computing device6.

Preferably, the routing and distribution of application level support for each traffic flow is distributed to provide efficient routing and processing. For example, if the traffic flow represented by the solid line was the first of the three traffic flows initiated, the application level support was distributed evenly between routing nodes10A,10D, and10C. If the traffic flow represented by the dashed line was the second flow initiated, the application level support for the traffic flow may have been evenly distributed between routing nodes10A and10B. When the traffic flow associated with the dotted line was initiated, a decision may have been made to avoid providing application level support by routing node10A, due to its handling of the traffic flows represented by the solid and dashed lines. Thus, for the traffic flow represented by the dotted line, routing node10A only forwards the traffic, wherein routing nodes10B and10C were less congested and had sufficient capacity to handle the application level support.

Notably, distribution of the processing associated with application level support may be distributed based on available resources or in an effort to maximize routing or processing speeds by distributing the processing among multiple routing nodes10. The basic process of distributing application level support during routing is outlined inFIG. 2. Preferably, the process will begin by identifying the necessary processing resources required for delivery of traffic from a source to the destination (block100). As in the network2depicted inFIGS. 1A through 1D, multiple routing paths will likely exist. Among these multiple paths, paths capable of providing the requisite application level support during routing between the source and destination are identified (block102). Within the identified paths, available processing resources are identified to assist in distributing the application level support (block104).

A routing path for delivering traffic between the source and destination is selected (block106), preferably based on available resources and perhaps based on other network conditions bearing on the processing and routing performance for the particular traffic flow, for the network in general, or a combination thereof. The ultimate goal is to provide the necessary application level support during routing and to route the traffic to meet quality and/or speed requirements. For example, streaming media traffic requiring application level support may need the traffic delivered with minimal packet loss and at a given rate. Other traffic flows may require less speed and more accuracy. The distribution of the application level support will facilitate meeting the routing and processing demands of the traffic flows.

Preferably, once the path is selected for traffic delivery, the necessary resource allocation for providing the application level support along the selected path is determined (block108). In essence, the distribution of the application level support is determined. The routing nodes needed to provide the application level support are determined, and the amount of application level support provided by each of the routing nodes10is defined. Based on this distribution, resources may be reserved in the selected routing nodes10to ensure each of the routing nodes have the capacity and the ability to provide the application level support for the traffic flow (block110). Once the resources are reserved, traffic for the traffic flow may be transported from the source to the destination along the selected path (block112).

During transport, the selected routing nodes10will provide the allocated application level support and routing functions necessary for delivery. The routing nodes10may cooperate with one another alone or in combination with a communication server8to communicate capacity information using an acceptable protocol. The capacity information is used to determine whether a given flow may be processed in a node or nodes within the routing path. Processing is allocated and the capacity is reserved for the allocated processing prior to initiating traffic flow.

With reference toFIG. 3, a routing node10is illustrated according to a preferred embodiment of the present invention. As noted above, the routing node10may be divided into three primary processing planes: a control plane12, a compute plane14, and a forward plane16. Preferably, all incoming packets are received by the forward plane16through various ports interacting with a network, such as a packet-switched network. The forward plane16is configured to analyze each of the incoming packets and determine where to send each packet. In general, the incoming packets need to be forwarded on toward their final destination, to the control plane12, or to the compute plane14.

Depending on the extent or nature of any necessary manipulation of the packet, the packet may be processed by the forward plane16and forwarded to the next-hop routing node or final destination. Preferably, any packet processing provided by the forward plane16is limited to manipulating information in one or more headers of the packet as necessary in traditional routing. As depicted inFIG. 4, packets requiring only traditional routing are maintained in the forward plane16for processing and immediately forwarded to the next-hop routing node or destination.

Packets entering the forward plane16that require application level processing, which may entail manipulation of the packet's payload, are directed to the compute plane14by the forward plane16. As depicted inFIG. 5, these packets are passed through the forward plane16to the compute plane14for processing and then sent back to the forward plane16, which will forward the processed packet to the next-hop routing node or final destination.

Although additional detail is provided below, the compute plane14provides application level processing, and any necessary payload manipulation required by such processing. During processing by the compute plane14, the payload may be reviewed, removed, modified, and repacked as directed by any number of applications. The routing node10preferably supports programming and unique configuration of the compute plane14and the forward plane16.

Any number of applications may be supported through the compute plane14. For example, Internet Protocol (IP) security and secure socket layer (SSL) applications may be implemented in a routing node10using the compute plane14. Various types of multimedia applications are made possible, alone or in combination with other applications. Further, incorporating a high-speed compute plane14for application specific packet processing enables streaming applications and minimizes or eliminates the need for buffering. The compute plane14is capable of implementing virtually any type of application, ranging from carrying out mathematical operations on payloads to implementing compression and encryption algorithms. The compute plane14may also help facilitate high-speed firewalls acting as a single point of entry or distributed to provide multiple points of entry. Typically, the compute plane14operates on layer four and higher protocols that are typically application related.

In addition to traditional forwarding of incoming packets and directing packets to the compute plane14for processing, the forward plane16may direct selected incoming packets to the control plane12for basic communications with the routing node10as shown inFIG. 6. In essence, the control plane12provides overall control and configuration for the routing node10, and in particular, for the compute plane14and the forward plane16. This control may range from running diagnostics to setting configurations for the compute plane14and the forward plane16. These settings may dictate the type of processing to carry out on the incoming packets and which plane handles the processing.

Returning now toFIG. 3, the routing node10may support various services, which are groups of code or objects that implement specific functionality. Preferably, these services use Java code and may be divided into compute services18related to the compute plane14, and network services20related to the operation of the forward plane16. Each of these services cooperates with the corresponding compute plane14and forward plane16via a compute application program interface (API)22and network API24, respectively. The network API can be CPIX, IEEE 1520, the IETF's APIs, or other propriety APIs. Since the services are preferably Java compatible, the compute API22and network API24may specify interfaces for Java applications to control the respective compute plane14and forward plane16.

Preferably, the network API24can be used to instruct the forward plane16to alter packet processing through the installation of hardware or software filters that facilitate forwarding rules. These filters execute actions specified by a defined filter policy. Typically, these filters can be based on combinations of fields in the machine address, IP address, and transport headers. The filters may also be configured to trigger on a payload as well. The filter policy can define where the matching packets are delivered and can also be used to alter the packet content as noted above.

Typical packet delivery options include discarding matching packets and diverting matching packets to the control plane12or compute plane14based on the filter policy. With the present invention, a high-speed compute plane14is provided to handle such processing. Additionally, packets may be “copied” to the control or compute planes12,14or may be mirrored to a selected interface. Packets may also be identified as being part of high-priority flow; these packets can be placed in a high-priority queue and delivered accordingly. For example, packets can be marked differentially for DiffSery or MPLS marking. As noted, the filter policy can also cause packet and header content to be selectively altered for most of these operations. The particular plane handling the processing is capable of re-computing IP header check sums at high speeds when and if the IP header or payload is changed.

In the present invention, all control plane computations, such as installing new routing tables, ARP cash tables, Filter tables, or parsing a new Internet Control Message Protocol (ICMP) message type, are easily accommodated through the network API24. Through the network API24, the forward plane16may provide a number of services. The applications are typically contained within the forward plane16and will not require additional processing by the compute plane14for traditional operation. The following list of services is merely exemplary and not intended to limit the scope of the present invention. The various functions provided by the forward plane16relate to analyzing incoming packets, manipulating packet headers, if necessary, and forwarding the packets to the next-hop or destination at high speeds.

The present invention supplements these abilities with high-speed, preferably line rate, processing capabilities at an application level. As noted, the compute plane14is preferably used to manipulate packet data or payloads beyond layer three or four protocols that provide application layer support. Thus, instead of analyzing or modifying the header on a packet, data analysis and manipulation associated with application layers in the packet is possible in the compute plane14.

The compute plane14provides application support efficiently and at high speeds without impacting the traditional routing speeds of the forward plane16. Further, the application layer processing is provided at much faster speeds in the compute plane14than would be possible in the control plane12. In addition to increased routing speeds and efficiency for application support, the compute plane14allows significant configuration of routing nodes10to facilitate any number of applications or combinations thereof.

Overall interaction between the control plane12, compute plane14, and forward plane16is outlined in the flow diagram ofFIG. 7. Notably, the preferred processing for each of the three planes is illustrated. The process begins (block200) with the forward plane16receiving all incoming packets regardless of whether the packets are intended for the routing node directly or simply sent to the routing node for routing. When a packet is received (block202), the forward plane16will filter the packet based on the forwarding rules (block204).

In general, the forwarding rules will dictate whether the packet is forwarded to the control plane12, compute plane14, or sent to the next-hop or destination after processing by the forward plane16(step206). As discussed above, packets directed to the routing node10, such as those used for diagnostics or to set configurations, are directed to the control plane12. Packets requiring application level processing are sent to the compute plane14. Packets for which the forward plane16can handle all processing are simply processed in the forward plane16and forwarded to the next-hop or destination. Typically, packets processed by the compute plane14and forward plane16are those requiring routing.

Assuming that the packet is one capable of being handled solely by the forward plane16, the packet is processed accordingly in the forward plane16(block208) and forwarded to the next-hop or destination (block210). As noted, packet processing in the forward plane16is typically limited to header analysis and manipulation.

If the packet received by the forward plane16is determined to be one directed to the control plane12based on the forwarding rules (block206), the packet is received by the control plane12(block212) and processed by the control plane12accordingly (block214). As noted, packets intended for the control plane12may facilitate diagnostic or control instructions for the compute plane14, such as instructions to set particular configurations for the compute or forward planes14,16. For example, the compute plane14may receive information for establishing the forwarding rules for the forward plane16as well as configure the particular processing carried out by the compute plane14or the forward plane16.

When the control plane12needs to respond to communications or deliver instructions to another network device, the control plane12will prepare a suitable packet or response for sending to a select destination (block216). Preferably, the packet or packets associated with an outgoing communication from the control plane12are sent to the forward plane16wherein the packet or packets are forwarded to the next-hop or destination (block210).

If the packet received by the forward plane16from the network is one requiring application level support and the forwarding rules direct the packet to the compute plane14(block206), the packet is routed to the compute plane14accordingly. As described in further detail below, the forwarding rules may dictate where to send the packet within the compute plane14or how the packet will be processed once it is received by the compute plane14. In general, the compute plane14receives the packet (block218) and processes the packet as dictated by the application (block220). As noted, preferably the application data or payload is processed in the compute plane14.

In particular, the compute plane14is configured to carry out select functions to facilitate application level processing, which results in data or payload manipulation (block220). The processing may require restructuring or re-packetizing the data or payload information depending on the particular application. Certain applications may simply process individual packets wherein other applications may require various types of data or payload reconstruction. For example, information in one packet may be used to create multiple new packets, or the information in multiple packets may be used to create a single packet. Regardless of the processing, the packets processed or provided by the compute plane14are sent to the forward plane16(block222) for forwarding to the next-hop routing device or destination. As such, the forward plane16will receive packets from the compute plane14and forward the packet to the next-hop or destination (block210).

With regard to distributing processing among routing nodes10, the control planes12of the routing nodes10will preferably cooperate with other routing nodes10or with the communication server8. The communications may provide information bearing on the processing capacity available and the type of application level support provided by the particular routing node10. Based on this information, resources may be allocated and reserved as necessary to handle forwarding provided by the forward plane16and processing provided by the compute plane14. Those skilled in the art will recognize various techniques and protocols, such as RSVP, or COPS capable of facilitating allocation and reservation of resources for traffic flows. RSVP is a resource reservation setup protocol for the Internet. Its major features include: (1) the use of “soft state” in the routers, (2) receiver-controlled reservation requests, (3) flexible control over sharing of reservations and forwarding of subflows, and (4) the use of IP multicast for data distribution. For additional information regarding RSVP, please see the Internet Engineering Task Force's RFCs 2205 through 2210 and 2748, which are incorporated herein by reference in their entirety. The communication server8may cooperate or may be one of various types of policy servers, call servers, and the like.

A block diagram of a preferred configuration of the routing node10is depicted inFIG. 8. Preferably, each of the control plane12, compute plane14and forward plane16includes dedicated processing capability and is in communication with the other planes through a switching backplane26. As such, the control plane12will include a control processor28associated with a backplane interface30coupled to the switching backplane26and will include sufficient memory32for storing the necessary instructions and data for operation.

The compute plane14includes a backplane interface34in communication with one or more high-speed compute processors (CP)36. These compute processors36will include or be able to carry out select processes, rules or functions38. Further, the compute processors36may stand alone or be controlled in part by a host processor40. Preferably, the host processor40is associated with sufficient memory42for storing the necessary data and instructions for operation. The host processor40may also be associated with a library module44, which may store various types of compute processor functions used to configure the function or rules38of the compute processors36. The speed of the host processor40is not as critical as insuring that the compute processors36are capable of high-speed processing.

In an effort to maximize the processing speeds, the compute processors36may be implemented using traditional central processing units (CPUs), field programmable gate arrays (FPGAs); application specific integrated circuits (ASICs); digital signal processing (DSP) components network processors; or a combination thereof. Preferably, each compute processor36will include a processor and an FPGA or ASIC cooperating to maximize processing throughput. The processor facilitates configuration of the cooperating FPGA or ASIC, while the FPGA or ASIC processes the packets. Notably, the compute processor36is a generic name for any one or combination of hardware, firmware or software capable of providing the high-speed application processing required in the compute plane14. Those skilled in the art will appreciate the numerous techniques available to provide high-speed processing.

The compute processor36is configured to carry out select functions or rules38at or close to wire-line speeds on the selected packets directed to the compute plane14from the forward plane16. Importantly, the compute processors36may provide a combination of functions for varying applications or may be configured wherein each compute processor36carries out a dedicated function or rule38. In the latter case, different compute processors36may facilitate different processing based on the function or rules38. As such, the packets sent to the compute plane14from the forward plane16are directed to a select compute processor36capable of handling the application associated with the given packet.

The forward plane16includes a backplane interface46for communicating with the switching backplane26. The backplane interface46of the forward plane16is associated with a forward processor48capable of implementing select forwarding rules50that facilitate packet filtering and delivery to the control plane12, compute plane14, and the next-hop or destination. The forward processor48provides the typical routing processing and functions in traditional fashion for those packets that do not require the application processing of the compute plane14. The forward processor48is also associated with a network interface52, which is coupled to the packet-switched network for receiving and sending packets.

The network interface52may be any type of network interface, including a 10 Base T, 100 Base T, gigabit Ethernet, 10 Giga, POS packet Over SONET, ATM, OC-3, OC-12, OC-48, OC-192, or other interfaces. As depicted, given the necessary volume of traffic handled by the routing node10, the forward plane16may be provided on multiple cards, all of which interface with the switching backplane26. These cards can be passive or active, and may include their own forward processors48and network interfaces52. Further, the compute plane14may be implemented on multiple cards in a fashion similar to that depicted for the forward plane16.

As with the compute processors36in the compute plane14, the forward processors48require high-speed processing capability. As such, the forward processor48is also a CPU, ASIC, FPGA, DSP device, network processor (NP), or combination thereof. Preferably, as with the compute processors36, the forward processors48are programmable in the sense that the forwarding rules50and basic processing configurations are programmable. Preferably, the compute processors36and the forward processors48are programmable and can be programmed under the control of the control plane12.

In essence, it is preferable for the control plane12to be able to establish the forwarding rules50and configure processing for the forward plane16. Similarly, the control plane12is preferably capable of setting the functions and rules38implemented by the compute processors36in the compute plane14. Those skilled in the art will appreciate the tremendous flexibility in programming and configuring the compute plane14and the forward plane16.

For example, assume that for a given media stream application level processing is required for type A packets and basic forwarding is required for type B packets. Configuration instructions may be sent to the routing node10defining the type A and B packets within the media stream and the processing function to provide on the type A packets. The configuration instructions may be sent in one or more packets, which will be forwarded to the control plane12by the forward plane16. Upon receipt, the control plane12will configure the forward plane16to recognize the type A and B packets in the media stream and forward the type A packets to the compute plane14and the type B packets on to the next-hop or the final destination.

Those skilled in the art will recognize improvements and modifications to the disclosed embodiments of the present invention. For example, the routing devices of the present invention may be any number of network devices, including routers, switches, gateways, aggregation devices, network distribution devices, core routers, wireless base stations, wireless access points, and multiplexors (electrical and optical). All such improvements and modifications are considered within the scope of the concepts disclosed herein and the claims that follow.