Internal load balancing in a data switch using distributed network processing

TECHNICAL FIELD

0001The present invention generally relates to switching device in a data communications network for distributing processing operations and therefore processing load between different packet processing elements. In particular, the invention relates to a system and method for allocating packet processing operations between ingress and egress processors to minimize load imbalances.

BACKGROUND

0002The distribution of network processing load within a networking device, such as a router or switch, is commonly fixed and largely determined by the architecture of the networking device. Depending on the manufacturer, for example, forwarding decisions and other packet processing is generally predetermined to be performed at either ingress or egress. As a result of the inherent asymmetric processing loads and asymmetric traffic patterns, the network processing load at the ingress point is rarely equal to the network processing load at the egress point in fact, the disparity in processing load between the ingress and egress is often so great that it is common for a processor at one side of the switch to struggle while a processor on the other side of the switch remains nearly idle.

0003Although some networking devices may share some processing load with other networking devices to balance the processing effort across the available processors, these schemes cannot dynamically balance the packet processing operations because: (a) network processing is typically accomplished by hard-wired application-specific integrated circuit (ASIC) devices, which are very good at repetitive tasks but generally lack the intelligence to alter the distribution of tasks dynamically; (b) network clusters employing distributed processing are designed to handle a set of large and fixed tasks, but are relatively slow and unsuitable for packet processing; and (c) most networking devices are simply over-engineered to accommodate the worst possible load with no consideration given to the excess computing capacity wasted at a system level.

0004There is therefore a need for a network switching device that can monitor for packet processing load imbalances and dynamically distribute the load between the ingress and egress processors to minimize the imbalance.

SUMMARY

0005The invention in the preferred embodiment features a switching device including a plurality of switching modules, each of the switching modules including at least one external port adapted to receive a packet or other protocol data unit (PDU); a packet classifier adapted to inspect the packet and identify one or more packet processing operations to apply to the packet based upon one or more packet properties and to identify a second switching module of the plurality of switching modules to which to forward the packet; a controller adapted to allocate each of the identified one or more packet processing operations between a first set of packet processing operations and a second set of packet processing operations, execute the first set of packet processing operations at the switching module including the external port at which the packet was received, and transmit a command to the second switching module instructing the second switching module to execute the second set of packet processing operations. The second switching module is adapted, like each of the plurality of switching modules in the preferred embodiment, to execute the second set of packet processing operations in response to the command, after which the packet may be transmitted to from external port towards its destination node.

0006In the preferred embodiment, the switching device is a router, bridge, or multi-layer switch while the packet processing operations are packet forwarding operations executed for purposes of preparing the packet for transmission to the next node in the direction of its destination node. In accordance with the preferred embodiment, packet processing operations are capable of being serially-distributed and executed at either an ingress switching module or an egress switching module of the plurality of switching modules. The packet processing operations are generally selected from, but not limited to, the group consisting of: header transformation, tag pushing, tag popping, quality of service, billing and accounting, Multi-Protocol Label Switching (MPLS) management, spanning tree operations, authentication, access control, higher-layer learning, alarm generation, port mirroring, source learning, class of service, color marking, and combinations thereof.

0007In the preferred embodiment, the method of allocating packet switching operations between a first switching module and a second switching module of a switching device comprises the steps of receiving a packet at an external port of the first switching module; identifying one or more packet processing operations for application to the packet; allocating each of the one or more packet processing operations between a first set of packet processing operations and a second set of packet processing operations; executing the first set of packet processing operations at the first switching module; and transmitting a command to the second switching module to execute the second set of packet processing operations. The method may further include the step of executing the second set of packet processing operations at the second switching module in response to the command.

BRIEF DESCRIPTION OF THE DRAWINGS

0008The present invention is illustrated by way of example and not limitation in the figures of the accompanying drawings, and in which:

0009<figref idref="DRAWINGS">FIG. 1</figref> is a functional block diagram of an enterprise switch, in accordance with the preferred embodiment of the present invention;

0010<figref idref="DRAWINGS">FIG. 2</figref> is a functional block diagram of a switching module of the enterprise switch for performing serially-distributed packet processing, in accordance with the preferred embodiment of the present invention;

0011<figref idref="DRAWINGS">FIG. 3</figref> is a functional block diagram of the databases retained in the local memory of a switching module, in accordance with the preferred embodiment of the present invention;

0012<figref idref="DRAWINGS">FIG. 4</figref> is a functional block diagram of a serially-distributed packet processing (SDPP) controller, in accordance with the preferred embodiment of the present invention;

0013<figref idref="DRAWINGS">FIG. 5</figref> is a schematic diagram of a header for distributing SDPP services between switching modules, in accordance with the preferred embodiment of the present invention;

0014<figref idref="DRAWINGS">FIG. 6</figref> is a flowchart of the method by which an ingress switching module processes an ingress flow, in accordance with the preferred embodiment of the present invention; and

0015<figref idref="DRAWINGS">FIG. 7</figref> is a flowchart of the method by which an egress switching module processes an egress flow, in accordance with the preferred embodiment of the present invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

0016Illustrated in <figref idref="DRAWINGS">FIG. 1</figref> is a functional block diagram of an enterprise switch. The enterprise switch <b>100</b> is one of a plurality nodes and other addressable entities operatively coupled to a data communications network embodied in a local area network (LAN), wide area network (WAN), or metropolitan area network (MAN), an Internet Protocol (IP) network, the Internet, or a combination thereof, for example.

0017The enterprise switch <b>100</b> preferably comprises a plurality of switching modules <b>110</b>-<b>113</b>, sometimes referred to as blades, which are seated into slots in the backplane <b>152</b>. Each of the switching modules <b>110</b>-<b>113</b> includes one or more external ports <b>102</b>, each of which may be operably coupled to another node in the data communications network via a communications link (not shown), as well at one or more internal ports operably coupling each switching module <b>110</b>-<b>113</b> to every other switching module via a shared switch fabric <b>150</b>.

0018A switching module <b>110</b>-<b>113</b> preferably comprises at least one network processor (NP) <b>106</b> capable of, but not limited to, at least Layer <b>2</b> (Data Link) and Layer <b>3</b> (Network) switching operations as defined in the Open Systems Interconnect (OSI) reference model. One possible Layer <b>2</b> protocol for operably coupling the external ports <b>102</b> to a wired and/or wireless communications link is the Institute of Electrical and Electronics Engineers (IEEE) 802.3 standard, while the set of possible Layer <b>3</b> protocols includes Internet Protocol (IP) version 4 defined in Internet Engineering Task Force (IETF) Request for Comment (RFC) 791 and IP version 6 defined in IETF RFC 1883.

0019For purposes of this disclosure, data flowing into a switching module <b>110</b>-<b>113</b> from an external port <b>102</b> toward the fabric <b>150</b> is referred to herein as ingress data which comprises ingress PDUs. The switching module through which ingress data propagates is referred to as the ingress switching module. In contrast, data flowing from the fabric <b>150</b> to an external port <b>102</b> is referred to as egress data which comprises egress PDUs. The switching module through which egress data propagates is referred to as an egress switching module. Each of the plurality of switching modules of the preferred embodiment may serve as both an ingress switching module and an egress switching module for purposes of different flows.

0020The enterprise switch <b>100</b> further includes a central command processor (CMM) <b>120</b> for managing various system resources including congestion monitoring and operational assignments discussed in more detail below. In the preferred embodiment, the CMM <b>120</b> is embodied in one of the plurality of switching modules <b>110</b>-<b>113</b>, although one skilled in the art will appreciate that the functions performed by the CMM may be executed by one or more entities incorporated in the backplane <b>152</b> and or a separate management module.

0021Illustrated in <figref idref="DRAWINGS">FIG. 2</figref> is a functional block diagram of a switching module for performing serially-distributed processing of PDU flows. The switching module <b>200</b> of the preferred embodiment, consistent with switching modules <b>110</b>-<b>113</b>, comprises one or more network interface modules (NIMs) <b>104</b>, one or more network processors <b>106</b>, a management module <b>220</b>, and a fabric interface module <b>208</b>. Each of the NIMs <b>104</b> is operatively coupled to one or more external ports <b>102</b> for purposes of receiving ingress data traffic and transmitting egress data traffic. The NIMs <b>104</b> preferably include one or more physical interfaces and media access control (MAC) interfaces adapted to exchange PDUs, e.g., Ethernet frames, via network communications links (not shown). Upon receipt, the ingress PDUs are conveyed from the plurality of NIMs <b>104</b> to the network processor <b>106</b> by means of one or more internal high-speed serial data buses <b>206</b>. The network processor <b>106</b> preferably classifies the ingress PDUs, performs any forwarding operations assigned for execution at ingress, and enqueues the PDUs in ingress queue memory <b>248</b> until bandwidth is available to transmit the PDU to the appropriate one or more egress blades via the switching fabric <b>150</b>.

0022With respect to egress operations, the switching module <b>200</b> is also adapted to receive egress PDUs from the switching fabric <b>150</b> and enqueue those PDUs in the egress queue memory <b>242</b>. The NP <b>106</b> of the switching module <b>200</b> at egress may perform one or more additional forwarding operations assigned to it before the PDU is committed to one of a plurality of queues in the buffer <b>250</b> and transmitted to the appropriate NIM <b>104</b> and corresponding egress port <b>102</b>. The plurality of queues in buffer <b>250</b> are actively monitored by a statistics manager <b>252</b> which compiles and transmits congestion information <b>254</b> to the CMM <b>120</b> via the management module <b>220</b>. The congestion information <b>254</b>, including queue depth for example, is used to characterize the egress flows, assess the congestion state of the module, and allocate packet processing operations between ingress and egress network processors.

0023The management module <b>220</b> generally comprises a policy manager <b>222</b> for retaining and implementing traffic policies uploaded to the switching module <b>200</b> by a network administrator via a configuration manager <b>224</b>. The policies generated by the policy manager <b>222</b> are also based in part on Layer <b>2</b> and or Layer <b>3</b> addressing information derived by source learning operations, which associate PDU address information with the external port <b>102</b> on which it was received. As discussed in more detail below, the management module <b>222</b> is also adapted to transmit updates <b>254</b> from the CMM to the network processor <b>106</b> so that that the ingress switching module <b>200</b> may execute some, if not all, of the packet processing operations at ingress before transmitting the PDU to one or more downstream switching modules. The updates <b>254</b> include the data used to populate the multiplicity of databases supporting the serially-distributed packet processing operations discussed in more detail below.

0024The NP <b>106</b> of the preferred embodiment is adapted to perform Layer <b>2</b> switching operations and Layer <b>3</b> routing operations using PDU properties associated with Layer <b>2</b> through Layer <b>7</b> as defined in the OSI network reference model. The NP <b>106</b> preferably comprises a classifier <b>230</b>, a serially-distributed packet processing (SDPP) controller <b>236</b>, and a queue manager <b>240</b>. The classifier <b>230</b> receives ingress PDUs from the data bus <b>206</b>, inspects the PDUs for one or more fields of interest, classifies the PDUs into one of a plurality of flows, and retrieves forwarding information from a forwarding table retained in high-speed local memory <b>232</b>. The forwarding information preferably includes, but is not limited to, a flow identifier and an egress port identifier, i.e., the identifier of external port from which the PDU is to be transmitted.

0025The forwarding information retrieved by the classifier <b>230</b> is transmitted to the SDPP controller <b>236</b> where it used to identify a first set of one or more SDPP operations to be performed at ingress. An SDPP operation as used herein refers to a packet processing operation or other forwarding operation that is performed on behalf of a PDU, in response to a PDU, or to facilitate the transmission of a PDU from the switching device <b>100</b>. The ingress switching module <b>200</b> or the CMM <b>120</b> may also identify a second set of SDPP operations to be performed at the egress switching module. As one skilled in the art will appreciate, an SDPP operation is susceptible to being executed at either the ingress switching module or the egress switching module. The range of possible SDPP services is discussed in more detail in relation to <figref idref="DRAWINGS">FIG. 5</figref>.

0026In general, the ingress switching module <b>200</b> may perform all, some, or none of the SDPP operations at the ingress switching module. Any SDPP operations executed for the PDU but not performed at the ingress switching module <b>200</b> are performed at the egress switching module prior to transmission of the PDU from the switching device <b>100</b>.

0027The allocation of SDPP operations between the first set one or more SDPP services applied to ingress and a second set of SDPP services to be performed by the egress switching module is dynamically determined on a per packet and or per flow basis.

0028In the preferred embodiment, the allocation of the SDPP services to be performed at ingress is determined as a function of the flow ID and congestion status of the ingress and egress switching modules. In some embodiments, the congestion status of the ingress and egress switching modules is periodically compiled by the CMM <b>120</b> and reported to each switching module so that each of the switching modules may dynamically determine the most beneficial allocation of SDPP services. In other embodiments, the optimum allocation of SDPP operations is determined by the CMM <b>120</b>, downloaded to each of the plurality of switching modules <b>110</b>-<b>113</b>, and retained in the in the form of an SDPP assignment table <b>238</b> retained in local memory <b>232</b>, as illustrated in <figref idref="DRAWINGS">FIG. 3</figref>, in conjunction with various shared databases discussed in more detail below.

0029This SDPP assignment table <b>238</b> may, for example, explicitly define the allocation of SDPP services for each pair of ingress and egress switching modules, for example, on a per flow or per packet basis. The SDPP assignment table may be updated at regular intervals, one or more times per second, to reflect changing traffic patterns and inter-blade load imbalances.

0030The SDPP services are apportioned, in the preferred embodiment, between ingress and egress depending on the relative congestion states of the ingress and egress switching modules. In particular, the SDPP assignments are designed to shift the processing load from the switching module with an over-utilized NP to the module with an under-utilized NP. The goal of the distribution of SDPP services is therefore to uniformly distribute the consumption of processing resources throughout the switching device <b>100</b> and thus minimize the probability of any of the switching modules <b>200</b> dropping PDUs due to excess traffic conditions. By optimizing the distribution of processing load, the switching device <b>100</b> may accommodate disproportionately high traffic conditions that may occur at certain ports, such as the port to which a client attaches or the port providing a gateway to the Internet for example, without the expense of over-engineering all the switching modules.

0031Illustrated in <figref idref="DRAWINGS">FIG. 4</figref> is a functional block diagram of an SDPP controller of the preferred embodiment. The SDPP controller <b>236</b> includes an ingress NP processor <b>410</b> and egress process <b>420</b> embodied in one or more hardware or software computing elements, the SDPP assignment table <b>238</b>, and one or more modules adapted to execute individual SDPP services <b>430</b>. The ingress NP processor <b>410</b> is adapted to receive the ingress PDU <b>460</b> and flow identifier <b>462</b> from the classifier <b>230</b> and to query the SDPP assignment table <b>238</b> for the SDPP service assignment applicable to the individual packet or flow. In the preferred embodiment, the allocation of SDPP service assigned to the ingress and egress switching modules is indicated by an SDPP identifier discussed in detail below. The PDU is subsequently processed at the ingress switching module <b>200</b> in accordance with the first set of SDPP services from among the complete selection of SDPP services <b>430</b>.

0032The PDU <b>464</b> and SDPP identifier <b>466</b> are then transmitted to the egress switching module to instruct the egress switching module to execute the second set of SDPP services <b>430</b> assigned to the egress switching module. In the preferred embodiment, the SDPP identifier <b>466</b> is appended to the PDU or a PDU descriptor by the operations SDPP tag generator <b>412</b> prior to its transmission to the switching fabric <b>150</b>. In other embodiments, the SDPP ID may be transmitted via an out-of-band communication channel, for example.

0033Upon receipt of a PDU <b>470</b>, or its descriptor, at the egress switching module, the egress processor <b>420</b> of the egress switching module removes the SDPP identifier <b>472</b>, the SDPP tag reader <b>422</b> determines the SDPP services specified by the SDPP identifier by querying the SDPP assignment table <b>238</b>, and the egress switching module executes the second set of SDPP services <b>430</b> needed to complete the forwarding operations necessary to transmit the PDU <b>476</b> in the direction of its final destination.

0034In the preferred embodiment, the listing of SDPP services <b>430</b> includes, but is not limited to the following forwarding operations: header transformation, tag pushing, tag popping, quality of service, billing and accounting, Multi-Protocol Label Switching (MPLS) management, spanning tree operations, authentication, access control, higher-layer learning, alarm generation, port mirroring, source learning, class of service, and color marking, and policing and shaping, for example.

0035Header transformation services <b>431</b> generally encompasses the steps of: (a) retrieving a PDU's next-hop address specifying the physical address of the next node in the path to the ultimate destination; (b) encapsulating the PDU with a header including a source address equal to the physical address of the switching device <b>100</b>, or the egress switching module, as well as a destination address equal to the physical address of the next-hop on the path to the ultimate destination; and (c) decrementing the time-to-live counter of IP packets, for example. The next-hop address may be retrieved from the forwarding table <b>302</b> of the local memory <b>232</b> (see <figref idref="DRAWINGS">FIG. 3</figref>) of either the ingress or egress switching modules provided the addressing information contained therein is exchanged or the tables regularly synchronized by the CMM <b>120</b> for example.

0036VLAN tag pushing services <b>432</b> generally include the steps of (a) identifying one or more VLAN identifiers (VIDs) based on PDU properties including, for example, the PDU source MAC address, destination MAC address, protocol, and ingress port; and (b) encapsulating PDUs with one or more VLAN tags. The appropriate tags may be retrieved from a VLAN association table <b>304</b> in local memory <b>232</b> (see <figref idref="DRAWINGS">FIG. 3</figref>) used to look-up a VID based upon one or more PDU properties, for example. VLAN tag pushing services may be executed at either the ingress or egress switching modules once the VLAN association table <b>304</b>, defined by the network administrator for example, is distributed to or otherwise synchronized between each of the plurality of switching modules <b>110</b>-<b>113</b> of the switch <b>100</b>.

0037VLAN tag popping services <b>433</b> include the step of removing one or more VLAN tags from PDUs if the switch <b>100</b> is the penultimate hop or as the PDUs transition from a public network to the untagged domain of a private network, for example. As with the VLAN tag pushing services <b>432</b> above, the VLAN popping rules embodied in the VLAN association table <b>304</b> are distributed between or otherwise shared by the plurality of switching modules <b>110</b>-<b>113</b>.

0038Quality of Service (QoS) operations <b>434</b> encompass the procedures for reserving network resources, including memory and bandwidth, for example, using a session setup mechanism such as Resource Reservation Protocol (RSVP), for example. QoS operations <b>434</b> also encompass the implementation of Integrated Services or Differentiated Services or both. With respect to Differentiated Services, various operations may be executed at either the ingress or egress switching module, these operations including but not limited to priority marking, packet policing, queuing, and scheduling operations. The implementation of Differentiated Service (DiffServ) may also include the identification of the service classes associated with different flows and the assignment of those flows to one of a plurality of tunnels dedicated to transmit the traffic of one of the service classes. The different service class tunnels are preferably MPLS tunnels associated with different IP headers used to encapsulate the PDUs, which may or may not include a preexisting IP header, as the PDUs enter a tunnel. In the preferred embodiment, the PDUs may be assigned to one of a plurality of MPLS tunnels by both the ingress and egress switching modules using procedures prescribed in the DiffServ models including those set forth in Internet Engineering Task Force (IETF) Request for Comment (RFC) <b>2474</b> and RFC <b>2475</b>, both of which are hereby incorporated by reference herein.

0039Billing and Accounting services <b>435</b> preferably include the steps of: (a) identifying customer traffic flows based upon PDU properties; (b) identifying the type or character of services rendered; and (c) generating cumulative charges based upon those services on a per-customer basis and or per flow basis. The identification and tracking of charges can be performed by either the ingress or egress switching modules having access to the local billing and accounting database <b>306</b> in memory <b>232</b> (see <figref idref="DRAWINGS">FIG. 3</figref>) provided the information is periodically exchanged between the plurality of switching modules or the local billing and accounting databases <b>306</b> of the plurality of switching modules <b>110</b>-<b>113</b> synchronized by the CMM <b>120</b>, for example.

0040MPLS management services <b>436</b> preferably include procedures for: (a) exchanging MPLS binding messages with adjacent label-switched routers (LSRs) using session-oriented protocols such as RSVP-related protocols, Session Initiation Protocol (SIP), or Label Distribution Protocol (LDP), for example; (b) determining whether to forward non-MPLS packets into an MPLS domain; (c) determining whether non-MPLS PDUs are members of a Forwarding Equivalency Class (FEC); (d) imposing an MPLS label on those PDUs that are members of a FEC; (e) determine whether the switching module is the penultimate hop for PDUs from the MPLS domain and popping the MPLS labels if necessary; and (f) fragmenting MPLS packets that exceed the maximum byte limitations of the communications links. The data required to manage the implementation of MPLS services—which includes criteria used to determine which FEC of which PDU is a member, the applicable label to apply, and the next-hop address—are centrally maintained by the CMM and distributed to the plurality of switching modules to enable both ingress and egress execution.

0041Spanning Tree services <b>437</b> generally encompass the methods for generating spanning trees needed to break the loops that give rise to broadcast storms. With respect to the network, the enterprise switch <b>100</b> is adapted exchange Bridge Protocol Data Units (BPDUs) with other nodes in the network. The BPDUs are used by the enterprise switch <b>100</b> to elect a root bridge and determine the shortest distance to the root bridge, for example. The response to the BPDUs of other switches may require that the switching modules of the switch <b>100</b> have access to a single shared database or maintain local copies of the shared spanning tree database <b>308</b> (<figref idref="DRAWINGS">FIG. 3</figref>) including a list of adjacent bridges and the ports through which they are reachable In the preferred embodiment, the spanning tree is generated by the CMM <b>120</b> and periodically downloaded to each of the switching modules <b>110</b>-<b>113</b>.

0042Each of the switching modules <b>110</b>-<b>113</b> in the preferred embodiment is further adapted to prevent the transmission of BPDUs and broadcast packets between different switching modules, or ports of the switching modules, if doing so would cause broadcast storms. As such, each of the switching modules <b>110</b>-<b>113</b> implements a light version of the spanning tree protocol used to identify which of the switching modules are within its broadcast domain and therefore able to receive a transmission without a broadcast storm. After the switching modules within the broadcast domain are identified, the switching module generally duplicates and transmits the BPDU to each of the identified switching modules. In the preferred embodiment, the process of reproducing the BPDUs and transmitting those BPDUs to other switching modules may be delegated from the ingress switching module to the egress switching if the egress switching module is in the same BPDU broadcast domain. A significant factor dictating where the reproduction of the BPDUs should occur is the availability of buffer space at the ingress and egress switching modules.

0043Authentication services <b>438</b> include procedures for determining which PDUs are to be granted admission and the level of access provided upon admission. In the preferred embodiment, each of the switching modules is adapted to consult an access control list (ACL) used to determine whether a received PDU is to be transmitted to its destination address or filtered. The ACL in the preferred embodiment regulates access based upon one or more PDU properties, preferably Layer <b>2</b> and Layer <b>3</b> properties including the source and destination address, the broadcast bit, the protocol type in order to guard against denial of service attack using Internet Control Message Protocol (ICMP) messages or Internet Group Management Protocol (IGMP) packets—as set forth in RFC <b>2402</b>, <b>2463</b> and <b>1826</b>—including authentication headers, for example. As above, each of the switching modules <b>110</b>-<b>113</b> may maintain an ACL <b>310</b> (<figref idref="DRAWINGS">FIG. 3</figref>) including user MAC and or IP addresses, passwords, and associated access privileges.

0044Access Control services <b>439</b> encompasses secondary forms of authentication services which regulate access based upon higher layer properties. In the preferred embodiment, Access Control services <b>439</b> pertains to the grant or denial of access based upon: (a) protocol ID, thereby allowing the switching device <b>100</b> to counter denial of service attacks using ICMP and IGMP packets, for example, without authentication headers; (b) port number for protocols that uses them including File Transfer Protocol (FTP), Trivial File Transfer Protocol (TFTP), telnet, and instant messaging, for example; and (c) application headers to filter out undesirable applications such as peer to peer file exchanges. In some embodiments, the Access Control services <b>439</b> are used to supplement the Authentication services <b>438</b> and may be performed at either the ingress or egress switching module anytime after initial authentication services <b>438</b> have been performed.

0045Higher-Layer Learning services <b>440</b> include the steps of reporting information learned at a network interface to applications in the switching device <b>100</b> concerned with higher-layer operations. MAC addresses learned through Address Resolution Protocol (ARP) messages, for example, are reported to an ARP table <b>312</b> retained in local memory <b>232</b> (<figref idref="DRAWINGS">FIG. 3</figref>) and periodically updated via exchanges between the plurality of switching modules <b>110</b>-<b>113</b> or with the CMM <b>120</b>.

0046Alarm services <b>441</b> refer to system-wide checks used to notify applications on the switch <b>100</b> of conditions that warrant the attention of the CMM <b>120</b> or network administrator, for example. These conditions may include, for example, situations in which PDUs having the same source address are received on a plurality of ports.

0047Port Mirroring services <b>442</b> refers to procedures for duplicating PDUs received on one port and transmitting those PDUs to a traffic analysis tool on a designated port by the network administrator, for example.

0048Source Learning <b>443</b> generally refers to the process of: (a) associating a PDU's source address with the ingress port on which it was received; (b) recognizing situations in which PDUs having the same source address are received on different ports; and (c) determining whether to reject a PDU received on one port but previously learned on another or to allow the PDU and simply age-out the previously learned association. The source learning table <b>314</b> (<figref idref="DRAWINGS">FIG. 3</figref>) compiled by each of the switching modules <b>110</b>-<b>113</b> may be periodically exchanged between the switching modules <b>110</b> (-<b>13</b> to provide each module access to source learning port associations independent of whether the source learning services <b>443</b> were executed at either ingress or egress.

0049Class of Service (CoS) <b>444</b> operations pertain to the procedures for (a) determining, at the ingress or egress switching module, whether a PDU is to be filtered in the preference of another based on one or more criteria including the inbound PDU's IEEE 802.1p priority value, for example, and (b) queuing PDUs of one or more flows at either the ingress or egress switching module and subsequently releasing the PDUs of the application level flows with a scheduler in accordance with the class of service requirements of the flows. The classification criteria used to identify and provision CoS are collectively referred to as classification rules. In the preferred embodiment, the CMM maintains a comprehensive database including the classification rules and the applicable classification data disseminated to the plurality of switching modules <b>110</b>-<b>113</b> at periodic intervals or when needed.

0050Coloring Marking <b>445</b> services are used to (a) determine, at the ingress or egress switching module, whether to pass, filter, or re-color PDUs with a tri-color marker previously applied by an upstream node in the network, and (b) implement a token bucket algorithm for appending, at the ingress or egress switching module, a tri-color marker to the PDUs to assist downstream nodes in selectively filtering the packets as needed. Coloring Marking <b>445</b> services encompasses both Two Rate Tri-Color Marker (trTCM) and currently embodied in an IETF publication authored by Osama Aboul Magd, and includes Single Rate Tri-Color Marker (srTCM) in an IETF publication drafted by Juha Heinanen, both of which are hereby incorporated by reference herein.

0051Illustrated in <figref idref="DRAWINGS">FIG. 5</figref> is a schematic diagram of an SDPP tag for transmitting packet data between switching modules. The SDPP tag <b>510</b> in the preferred embodiment is appended to a PDU <b>500</b> or PDU descriptor by the SDPP tag generator <b>412</b> of the ingress switching module <b>200</b> and read by the SDPP tag reader <b>422</b> of the egress switching module. The SDPP tag <b>510</b> in the preferred embodiment comprises an SDPP identifier (ID) <b>512</b> and an op-code <b>502</b>.

0052As discussed above, the SDPP ID <b>512</b> serves as a command used to instruct the egress switching module that receives the PDU to perform one or more forwarding operations on behalf of the ingress switching module. In other words, the SDPP tag in the preferred embodiment provides the signaling mechanism by which an ingress processor serially-distributes one or more PDU forwarding operations to an egress processor, thereby reducing the processing load experienced by the ingress processor. In the preferred embodiment, the SDPP ID <b>512</b> is retrieved at ingress from the SDPP assignment table <b>238</b>, although it may also be determined dynamically as a function of the processing load in one or more switching modules <b>110</b>-<b>113</b>.

0053In some embodiments, the SDPP ID <b>512</b> comprises a flow ID <b>504</b> and a source processor ID <b>506</b>. The flow ID <b>504</b> uniquely defines a stream of one or more PDUs having the same SDPP service processing requirements, while the source processor ID <b>506</b> indicates the NP <b>106</b> of the ingress switching device <b>200</b> from which the PDU was received. The switch <b>100</b> may use the flow ID <b>504</b> and source processor ID <b>506</b> together to uniquely define the particular SDPP services to apply to or execute on behalf of the associated PDU <b>500</b>.

0054The SDPP tag <b>510</b> in some embodiments further comprises an operations code, i.e., op-code <b>502</b>. The term op-code as used herein refers to a command that causes an egress switching module to be configured to execute the forwarding operations specified by the SDPP ID of one or more PDU flows associated with the op-code. Upon receipt of an op-code, the egress NP loads one or more computer readable instructions to the NP's on-chip cache (not shown) or other local memory <b>232</b>. Since the on-chip cache of most NPs is too small to retain the computer readable instructions needed to process every possible flow seen by the switch <b>100</b>, the op-code <b>502</b> is used to load only those programmatic instructions needed to execute the SDPP services for the limited number of flows transmitted to the particular egress NP which is a subset of flows supported by the switch <b>100</b>. As such, different instruction sets maybe uploaded to the NP of different switching modules <b>110</b>-<b>113</b> to optimize the forwarding operations at each of the particular NPs <b>106</b>. The instructions sets of the individual NPs <b>106</b> may also be updated at-will as traffic changes by merely issuing a new op-code.

0055By way of example, an op-code may be issued by an ingress switching module instructing the egress NP <b>106</b> to cache all executable codes or algorithms necessary to processing one or more flows in accordance with an MPLS protocol. Once the executable codes associated with the particular op-code <b>502</b> are cached, each of the subsequent PDUs having a flow ID <b>404</b> specifying an MPLS processing operation may be subjected to the same processing regime until a new op-code is received.

0056The switching modules <b>110</b>-<b>113</b> of the switch <b>100</b> in some embodiments are adapted to collectively process batches of packets, i.e., a plurality of packets associated with one or more PDU flows. To execute batch processing, a SDPP tag <b>510</b> including an op-code <b>502</b> and SDPP ID <b>512</b> is transmitted with the first packet of a plurality of related packets. Thereafter, the SDPP tag <b>510</b> applied to the related packets need only include the SDPP ID <b>512</b>. The egress switching module then subjects each of the plurality of PDUs to the processing regime specified by its SDPP ID <b>510</b> and the computer readable instructions specified in the first of the plurality of PDUs. In this manner, the need to transmit the op-code <b>502</b> with each of the plurality of PDUs is obviated and the resources needed to append, transmit, and read the op-code <b>502</b> is reduced.

0057In an alternative embodiment, the SDPP ID <b>512</b> and or op-code <b>502</b> are transmitted from the ingress switching module to the egress switching module using an out-of-band communication channel (not shown). The out-of-band communication channel corresponds to a signaling channel, e.g. a bus, different from the data channels used to transmit PDUs between switching modules.

0058Illustrated in <figref idref="DRAWINGS">FIG. 6</figref> is a flowchart of the method by which an ingress switching module processes an ingress flow. Upon receipt of an ingress PDU (step <b>610</b>), the ingress switching module in the preferred embodiment classifies the PDU to identify the egress switching module to which it will be transmitted. Knowing the egress switching module, the ingress switching module can determine (step <b>640</b>) the relative demands placed on the ingress and egress switching modules and the need for load balancing. The PDU processing load experienced by the ingress switching modules (step <b>620</b>) and egress switching module (step <b>630</b>) may be acquired, in some embodiments, by the CMM <b>120</b> from the congestion states of the modules themselves. If the congestion state of the ingress switching module is over-utilized relative to the egress switching module, the load balancing change inquiry (testing step <b>650</b>) is answered in the affirmative and the distribution of SDPP services performed between ingress and egress altered (step <b>660</b>) to reduce the load imbalance. If the ingress switching module is relatively overloaded, for example, the percentage of the total SDPP services allocated to the egress switching module may be increased in proportional to the degree of imbalance. In the case of a severely overloaded ingress switching module, all the SDPP services may be allocated to the egress switching module. If the load experienced by the ingress and egress switching modules are substantially equal and the different within a predetermined load differential threshold, the load balancing change inquiry (testing step <b>650</b>) is answered in the negative and the pre-existing distribution of SDPP services is maintained.

0059After the allocation of SDPP services has been determined, the ingress switching module executes (step <b>670</b>) the subset of SDPP services designated for ingress. The remaining SDPP services to be executed at egress are specified in the one or more fields of the SDPP tag appended (step <b>680</b>) to the PDU prior to the transmission (step <b>690</b>) of the PDU to the egress switching module. If the egress switching module is severely congested due to other traffic conditions, for example, the ingress switching module may perform all SDPP services required by the PDU and the SDPP ID appended to the packet have a null value indicating the absence of any SDPP processing at the egress switching module.

0060Illustrated in <figref idref="DRAWINGS">FIG. 7</figref> is a flowchart of the method by which an egress switching module processes an egress flow. Upon receipt (step <b>710</b>) of a PDU from the switching fabric <b>150</b>, the module inspects the PDU for the presence of an SDPP tag <b>510</b> and reads the fields contained therein. If the SDPP tag <b>510</b> is present, the SDPP tag inquiry (testing step <b>720</b>) is answered in the affirmative and the SDPP tag removed (step <b>730</b>) for inspection. If the SDPP tag includes an op-code <b>502</b>, the op-code inquiry (step <b>740</b>) is answered in the affirmative and the computer readable instructions indicated by the op-code loaded (step <b>750</b>) into cache in the egress network processor. In the absence of an op-code within the SDPP tag, the op-code inquiry (step <b>730</b>) is answered in the negative and the NP <b>106</b> executes (step <b>760</b>) the second set of SDPP services identified by the SDPP ID <b>512</b> in accordance with the instruction set specified by the op-code of a preceding PDU of the same batch. The PDUs processed in accordance with the SDPP service requirements are then transmitted (step <b>770</b>) from the egress switching module in the direction of the PDU's destination node. As one skilled in the art will appreciate, the PDUs processed at a egress network processor undergo the same packet processing and appear substantially identical to PDUs processed at either the ingress or egress switching module alone.

0061Although the description above contains many specifications, these should not be construed as limiting the scope of the invention but as merely providing illustrations of some of the presently preferred embodiments of this invention.

0062Therefore, the invention has been disclosed by way of example and not limitation, and reference should be made to the following claims to determine the scope of the present invention.