CN103746931B - A kind of method for computer network, the network equipment and service card - Google Patents

Abstract

In general, techniques for maintaining load balancing after service applications are described. A network device including an ingress forwarding component and an egress forwarding component and a service card may implement the technique. The ingress forwarding component receives the packet, and in response to a determination that a service is to be applied to the packet, updates the packet to include an ingress identifier identifying the ingress forwarding component, and thereafter transmits the updated packet to the service card. The service card applies the service to the updated packet to generate a serviced packet, and transmits the serviced packet to the ingress forwarding component identified by the ingress identifier so as to maintain load balancing of the packet flow across the plurality of forwarding components . The ingress forwarding component determines a next hop to forward the serviced packet to, and the egress forwarding component forwards the serviced packet to the determined next hop.

Description

Method, network equipment and service card for computer network

technical field

This disclosure relates to computer networks, and more particularly to load balancing within computer networks.

Background technique

A computer network is a collection of interconnected computing devices capable of exchanging data and sharing resources. In a packet-based network, computing devices communicate data by dividing the data into small chunks called packets, which are individually routed across the network from a source device to a destination device. The destination device extracts the data from the packets and assembles the data into its original form. Dividing the data into packets enables the source device to retransmit only those individual packets that may have been lost during transmission.

Network routers maintain routing information, which describes available routes through the network. When a packet is received, a router examines the information within the packet and forwards the packet based on the routing information. In order to maintain an accurate representation of the network, routers exchange routing information according to one or more routing protocols, such as Interior Gateway Protocol (IGP) or Border Gateway Protocol (BGP).

In some instances, routers may implement a form of load balancing referred to as Weighted Equal Cost Multi-Path (WECMP) to distribute packet flows across multiple paths through the network to the same destination device. That is, a computer network can provide for multiple paths between ingress routers and egress routers. An ingress router may choose one of these paths for a particular packet flow and another path for another packet flow, which may be equal in cost or other metrics. In selecting these paths, the ingress router may attempt to distribute the packet flows across the paths in order to avoid overdistributing the packet flows to any one path. This form of load balancing can be weighted because the ingress router can assign weights to each path and dispatch packet flows according to the assigned weights.

Routers may also implement services such as security services, network address translation (NAT) services, tunneling services, firewall services, and the like. Typically, an ingress router applies the some services. However, application of these services may disturb packet forwarding according to WECMP, so that routers do not perform proper load balancing to distribute packets of flows according to defined weights.

Contents of the invention

Generally, a technique is described for enabling a network device to perform load balancing of a packet flow following application of one or more services to the packet flow. Rather than updating the service card to perform routing, or otherwise hashing at least a portion of the packet to pseudo-randomly identify a forwarding component capable of performing routing, an ingress forwarding component of a network device that receives a packet may mark, tag, or This packet is otherwise updated to specify an ingress identifier identifying the ingress forwarding component. As a result, the service card of the network device may transmit the serviced packet back to the forwarding component identified by the ingress identifier after applying one or more services to the received packet. This ingress forwarding component may be configured to appropriately apply a Weighted Equivalent Multi-Path Algorithm (WECMP) when one of multiple paths (often of equal cost) along which a served packet is forwarded is determined.

This technique can enhance cost savings by potentially avoiding service card updates to perform this routing. Additionally, the technique may facilitate load balancing in accordance with WECMP by enabling the service card to discard a hash of a packet to pseudo-randomly identify a forwarding component that will act as an ingress forwarding component for the packet, but is not configured to perform path selection in accordance with the WECMP algorithm . Although described with respect to WECMP, the technique may generally be performed with respect to any load balancing algorithm, such as those utilized in performing link aggregation and other forms of multipath or multilink load balancing.

In one aspect, a method includes receiving a packet with a first forwarding component of a plurality of forwarding components included in a network device, wherein the first forwarding component of the plurality of forwarding components acts as a forwarding component for the received packet. The ingress forwarding component of the corresponding packet flow. The method further includes: determining, with the ingress forwarding component, that a service is to be applied to the packet; updating, with the ingress forwarding component, the packet to include an ingress identifier identifying the ingress forwarding component as a reference to determining that the service is to be applied to the packet responding; and transmitting the updated packet to the service card of the application service with the ingress forwarding component. The method also includes: applying the service to the updated packet with the service card to generate a serviced packet; and transmitting, with the service card, the serviced packet to the ingress forwarding component identified by the ingress identifier, so as to A forwarding component maintains load balancing of the packet flow. Additionally, the method includes: determining, with the ingress forwarding component, a next hop of a plurality of next hops to which to forward the serviced packet; and forwarding, with a second forwarding component of the plurality of forwarding components, the serviced packet to the determined next hop, wherein the second forwarding component of the plurality of forwarding components acts as an egress forwarding component for a packet flow to which the served packet corresponds.

In another aspect, a network device includes a plurality of forwarding components, wherein a first forwarding component in the plurality of forwarding components receives a packet, and acts as an ingress forwarding component for a packet flow corresponding to the received packet, and determines that the service will is applied to the packet, responsive to a determination that the service is to be applied to the packet, updating the packet to include an ingress identifier identifying the ingress forwarding component, and transmitting the updated packet to the service card to which the service is applied. The network device further includes a service card that applies the service to the updated packet to generate a serviced packet, and transmits the serviced packet to the ingress forwarding component identified by the ingress identifier, so as to facilitate forwarding across multiple A forwarding component maintains load balancing of the packet flow. The ingress forwarding component determines a next hop of a plurality of next hops to forward the served packet to. A second forwarding component of the plurality of forwarding components acts as an egress forwarding component for a packet flow to which the servicing packet corresponds, and forwards the serviced packet to the determined next hop.

In another aspect, a service card is configured to be inserted into a network device and coupled to a plurality of forwarding components of the network device, the service card comprising: a control unit acting as an ingress forwarding component for a packet flow corresponding to the packet A first forwarding component of the plurality of forwarding components receives a packet, wherein the packet includes an inner service packet header including a field specifying an ingress identifier that identifies the ingress forwarding component. The control unit executes a service engine that applies services to updated packets to generate serviced packets. The control unit further transmits the served packet to the ingress forwarding component identified by the ingress identifier so as to maintain load balancing of packet flow across the plurality of forwarding components.

The details of one or more embodiments of the technology are set forth in the accompanying drawings and the description below. Other features, objects, and advantages of the technology will be apparent from the description and drawings, and from the claims.

Description of drawings

FIG. 1 is a block diagram illustrating an example network system that performs service post-application load balancing in accordance with the techniques described in the disclosed disclosure.

FIG. 2 is a block diagram illustrating one of the routers of FIG. 1 in more detail.

3 is a block diagram illustrating the logical flow of packets through one of the routers of FIG. 1 according to the techniques described in this disclosure.

4 is a diagram illustrating an example service cookie used in accordance with the techniques described in this disclosure to specify a portal identifier.

5 is a flow diagram illustrating example operations of a network device in performing the post-service application load balancing techniques described in this disclosure.

6 is a block diagram illustrating an example network system that performs the post-service application load balancing techniques described in this disclosure in the context of an aggregated bundle of two or more links.

detailed description

FIG. 1 is a block diagram illustrating an example network system 2 that performs post-service application load balancing in accordance with the techniques described in this disclosure. Network system 2 includes network 6 that includes routers 10A-10E ("routers 10") that route network packets received from source devices 12A-12N ("source devices 12") toward destination device 14. . Network 6 may include a public network, such as the Internet, a private network, such as those owned and operated by a business or service provider, or a combination of both public and private networks. As a result, network 6 may alternatively be referred to herein as a service provider (SP) network. Network 6 may include one or more wide area networks (WANs), local area networks (LANs), virtual local area networks (VLANs), virtual private networks (VPNs), and/or other types of networks.

In some examples, network 6 may be an Internet Protocol network in which router 10 uses IP forwarding for transferring network packets. In other examples, network 6 may be a label switched network in which network devices such as router 10, often referred to as a label switched router or LSR, use the Multiprotocol Label Switching (MPLS) signaling protocol to establish labels A switched path (LSP), a label switched path is used to transport network packets received from source device 12 . The MPLS data transport mechanism of Network 6 can be viewed as lying between layers 2 and 3 of the Open Systems Interconnection (OSI) model, and is often referred to as a layer 2.5 protocol. References to layers followed by numbers may refer to specific layers of the OSI model. More information on the OSI model can be found in IEEE Transactions on Communications, Issue 4, Volume 28, dated April 1980, entitled "OSI Reference Model - the ISO Model of Architecture for Open Systems Interconnection" by Hubert Zimmermann found in IEEE Publication, which is hereby incorporated by reference as if fully set forth herein. Further information on MPLS and the various features of MPLS, as well as general architectural information on MPLS can be found in the Network Working Group of the Internet Engineering Task Force (IETF), dated January 2001, incorporated herein by reference , titled "Multiprotocol Label Switching Architecture" found in Request for Comments (RFC) 3031. In some instances, network 6 may provide generalized MPLS (GMPLS). Although described herein in some instances with respect to MPLS, the techniques of this disclosure are also applicable to GMPLS.

Thus, while shown in FIG. 1 as a single network 6, the network 6 may comprise any number of interconnected public or private networks, where the various networks are interconnected to form various virtual networks. In addition, network 6 may include various other network devices for forwarding network traffic, such as additional routers, switches or bridges. The particular configuration of network system 2 is just one example, and router 10 may be located within a single network or within multiple networks. Although described with respect to routers, aspects of the present technology are applicable to other network devices, such as bridges, switches, gateways, network caches, and network acceleration devices.

In the example of FIG. 1 , network system 2 includes a plurality of source devices 12 and destination devices 14 coupled to intermediate network 6 . Each of source device 12 and destination device 14 may be a personal computer, a laptop computer, a mobile phone, a VoIP phone, a television set-top box, a network device integrated into a vehicle, a video game system, a point-of-sale device, a personal digital assistant , an intermediate network device, a network appliance, a supercomputer, a mainframe computer, or another type of device that can be connected to the network 6 and communicate through the network 6 .

Source device 12 and destination device 14 are connected to network 6 via access link 5, which may comprise a wired and/or wireless communication link. As used herein, the term "communication link" includes any form of wired or wireless transmission medium and can include intermediate nodes such as network devices. Each access link 5 may comprise, for example, aspects of an asymmetric DSL network, WiMAX, T-1 lines, Integrated Services Digital Network (ISDN) or wired Ethernet.

Multiple physical and virtual communication links of network 6 interconnect routers 10 to facilitate control and data communications between the routers. The physical links of network 6 may include, for example, Ethernet PHYs, Synchronous Optical Network (SONET)/Synchronous Digital Hierarchy (SDH), Lambda, or other layer 2 data links that include packet transfer capabilities. Logical links of the network 6 may include, for example, Ethernet virtual LANs, MPLS LSPs or MPLS-TE LSPs.

Router 10 employs one or more Interior Gateway Protocols (IGPs) to determine link states/metrics for communication links within network 6 . For example, router 10A may exchange routing information with routers 10B-10E using Open Shortest Path First (OSPF) or Intermediate System-Intermediate System (IS-IS) protocols. Router 10A stores this routing information into a routing information base, which the router uses to calculate optimal routes to advertised destination addresses within network 6 .

In some examples, router 10 supports traffic engineering to improve utilization of paths through network 6 . In general, traffic engineering refers to the operation of diverting traffic flows away from the shortest paths computed by the IGP for the network 6, and toward potentially less congested, or otherwise more desirable (from operational point of view) moves across the physical path of the network. For example, routers 10 may use Resource Reservation Protocol with Traffic Engineering Extensions (RSVP-TE) or another label distribution protocol (e.g., Label Distribution Protocol (LDP)) to establish one or more LSPs connecting each pair of routers 10 tunnels to route network traffic away from network failures, congestion, and bottlenecks. Routers that include interfaces to LSP tunnels associate a metric with the LSP. The LSP metric may take the metric of the underlying IP path over which the LSP operates, or it may be configured to a different value by the administrator of the network 6 to influence the routing decisions of the router 10 . The routers 10 implement an interior gateway protocol to communicate via routing protocol messages and exchange the metrics established for the LSP tunnels and store these metrics in respective routing information bases that are used to calculate routes to the network 6 The best route for the advertised destination address. For example, router 10 may advertise an LSP tunnel as an IGP link of network 6 using OSPF forwarding adjacency (FA). Thus, as used herein, the term "link" or "communication link" may also refer to LSP operation over a Layer 2 communication link.

The LSP established by RSVP-TE uses the path state on the router 10 to reserve resources to ensure that such resources are available to facilitate Class of Service (CoS) for network traffic forwarded using the LSP. For example, router 10A may issue an RSVP path message toward router 10D to establish an LSP, and use the path state on both router 10A and router 10B to reserve a certain amount of bandwidth for the LSP. Routers 10A, 10B must maintain the reserved amount of bandwidth for network traffic mapped to an LSP until that LSP is preempted or torn down. RSVP-TE is more fully described in Awduche et al., "RSVP-TE: Extensions to RSVP for LSP Tunnels" in Request for Note 3209 of the Network Working Group of the Internet Engineering Task Force, December 2001, as text Incorporated by reference in its entirety.

In some examples, router 10 may use extensions to IGP to additionally distribute detailed information about network load. For example, router 10 may implement IS-IS with traffic engineering extensions that use new Type Length Values (TLVs). As another example, router 10 may implement OSPF with traffic engineering extensions using opaque link state advertisements (LSAs) to distribute link attributes in the link state advertisements in addition to link state and metrics. In some examples, router 10 may advertise the currently available bandwidth for links of network 6, which accounts for otherwise unaccounted for traffic. That is, the router 10 monitors and advertises the currently available bandwidth for a link expressed as a rate (e.g. MB/s), which takes into account The bandwidth to transmit Internet Protocol (IP) packets or LDP packets, where LDP packets are packets with accompanying labels distributed by LDP. The bandwidth currently available for a link is thus neither reserved nor used to transport traffic using unreserved resources. More information on this detail, new TLVs, extensions to opaque LSAs, and how routers may distribute this information is in the pending US Available in Patent Application Serial No. 13/536,487, the contents of which are hereby incorporated by reference in their entirety.

One or more routers 10 may also implement one or more services, often including one or more service cards to perform the services. These services may include, as some examples: deep packet inspection services, network address translation (NAT) services, firewall services, tunnel services, anti-malware services, anti-virus services, and encryption services. The application of some of these services can affect the path selection (or, in other words, the forwarding decision) performed by the packet forwarding component that originally received the packet. To illustrate, NAT services generally involve replacing a source address and/or source port specified in a packet's Internet Protocol (IP) packet header with a different source address and/or source port. When performing WECMP, routers can utilize so-called five-tuples that include both source port and source address when trying to distribute the packet flow to which the packet corresponds to two paths (often, of equal cost). Thus, routers that perform one or more services with respect to packets corresponding to flows that also actively span two or more paths and/or two or more links (such as in the example of aggregated links) For load balancing, the router typically must first forward the packet to the service card before performing path selection or forwarding decisions. However, service cards are typically not configured to perform path selection or make forwarding decisions. This lack of service card functionality may otherwise affect path selection and load balancing of packet flows across multiple paths and/or links.

To illustrate, router 10A may receive packet flow 22 from one of source devices 12A-12N, assuming router 10B applies one or more services to packets corresponding to packet flow 22. Router 10A may implement a load balancing algorithm, such as ECMP and/or WECMP, to send this packet to router 10B, specifically via one of links 15A, 15B, so as to facilitate Maintain a balanced load.

Router 10B may receive this packet, classify this packet as belonging to a flow for which both servicing and load balancing will be performed. Router 10B may then determine that the packet is sent first to a service card included in router 10B because router 10B is configured to apply the services first given that one or more services may influence the forwarding decision. The service card of router 10B can then receive this packet and apply the service. However, as noted above, the service card may not be configured or otherwise have this capability (eg, the requisite hardware and/or software). The service card can then apply a hash function to this serviced packet (such as the five-tuple noted above that includes both source address, source port, and destination address, destination port, and protocol) At least in part, to pseudo-randomly identify forwarding components capable of performing path selection. However, because this assigns this packet hash pseudo-randomly to one of the forwarding components, when sending these packets to router 10B via link 15A, 15B, the service card cannot guarantee the forwarding across loads in the manner previously ensured by router 10A. Components are balanced.

That is, the ECMP decision may have been performed by an external router, in this example router 10A, which is connected to router 10B via a number of links 15A, 15B. Router 10A may have used some algorithm to distribute the load between links 15A, 15B, such as WECMP. If the links fall on different forwarding components of the router, the traffic from different ingress forwarding components can go to the service card. If the volume of traffic to be served by the service card is high, the service card may need to distribute the load among the available forwarding components. To distribute this load, the service card may perform hashing on packet content (such as quintuples) to distribute these packets among the forwarding components. However, the administrator may have provisioned router 10A to perform load balancing between these links, which in turn distributes the load on the forwarding components of router 10B. When the service card hashes packets to distribute them pseudo-randomly back to the forwarding component, the service card may inadvertently modify the load balancing provided via router 10A, resulting in a load imbalance that does not follow the load balancing provided by router 10A . In this way, application of these services may disrupt packet forwarding according to WECMP, such that router 1OA does not perform to maintain proper load balancing.

According to the techniques described in this disclosure, after applying one or more services to the packet flow, router 10B (or any other of routers 10C-10E, or any other type of network device) can maintain the packet flow load balanced. Rather than updating the service card to perform routing, or otherwise hashing at least a portion of the packet to pseudo-randomly identify a forwarding component capable of performing routing, the ingress forwarding component of router 10B receiving the packet may mark, tag, or Other means update this packet to specify the ingress identifier that identifies the ingress forwarding component. As a result, the service card of router 10B may, after applying one or more services to the received packet, transmit the serviced packet back to the forwarding component identified by the ingress identifier so that when configured in router 10A WECMP load balances across forwarding components in a manner consistent with the administrator's intent. This technique can enhance cost savings by potentially avoiding service card updates to perform this routing. Additionally, by enabling the service card to discard the hash of the packet to pseudo-randomly identify the forwarding component acting as the ingress forwarding component for the packet, this technique can facilitate cross- Load balancing of the traffic of the ingress forwarding component. Although described with respect to WECMP, the technique may generally be performed with respect to any load balancing algorithm, such as those utilized in performing link aggregation, and other forms of multipath or multilink load balancing.

In operation, router 10B may receive a packet with a first forwarding component of a plurality of forwarding components. This first forwarding component may act as referred to as an "ingress forwarding component" for the packet flow, ie the packet flow 22 in the example of Fig. 1 to which the received packet corresponds. To act as an ingress forwarding component, this forwarding component can perform slow path processing to configure filters and other hardware logic so that packets corresponding to this flow 22 can be processed faster. This ingress forwarding component may install a filter for flow 22 indicating that one or more services are to be applied to packets corresponding to this flow.

Router 10A may distribute this flow 22 to link 15A using a load balancing algorithm, such as WEMCP which ensures proper load balancing. Proper load balancing may include assigning flows to links, such as links 15A, 15B, in a manner corresponding to the configured weights assigned to each of these links 15A, 15B. For example, a weight of 40 may be assigned to link 15A, and a weight of 60 may be assigned to link 15B, where a weight of 40 indicates that forty percent of all flows within the load-balanced subset of flows will be assigned to link 15A, while sixty percent of all flows in this load-balanced subset of flows will be allocated to link 15B. Router 10A may then maintain load balancing statistics to determine whether the actual distribution of flows to links 15A, 15B corresponds (typically within some defined threshold or percentage) to the weights assigned to the paths. In this manner, router 10A effectively load balances the flow across links 15A, 15B coupling router 10A to router 10B.

In any case, the ingress forwarding component of router 10B can determine that a service is to be applied to the packet. The ingress forwarding component may perform a lookup in a forwarding information base (FIB) using the 5-tuple included in the packet's IP header to determine that one or more services are to be applied to the packet. A FIB may represent a subset of a routing information base (RIB), where the control plane of router 10B may decompose the RIB to generate the FIB. This FIB typically includes an entry associated with the quintuple (or a part of it) specifying a so-called "next hop" to which the corresponding packet is to be forwarded. The FIB may also include an internal next hop, which identifies a service card and/or other type of card, or a component within router 10B to which the forwarding component will forward the corresponding packet. The FIB can also be configured with a series of next hops specifying a first internal component (such as a service card) by specifying the next hop of another network device such as router 10D followed by.

After identifying or otherwise determining that a service will be applied to the packet, the ingress forwarding component of router 10B may then update the packet to include an ingress identifier that identifies the ingress identifier in response to the determination that the service will be applied to the packet. Forward component. This ingress identifier may also be referred to as an ingress forwarding component identifier. The ingress forwarding component can set this identifier to directly identify the ingress forwarding component, or can specify the identifier so that it can be used in conjunction with a table or other data structure to resolve virtual identifiers assigned to the ingress forwarding component. Often, a virtual identifier is assigned and used to switch between the various packet forwarding components, where this virtual identifier identifies a slot or other coupling mechanism into which the ingress forwarding component plugs.

Once the packet is updated with the ingress identifier, the ingress forwarding component transmits the updated packet to the service card to which the service is applied. The service card then applies the service to the updated packet to generate a serviced packet and transmits the serviced packet to the ingress forwarding component identified by the ingress identifier. Therefore, instead of performing a hash on the packet's quintuple to pseudo-randomly assign the packet to any given one of the forwarding components, the service card uses the entry identifier to assign the packet to any given forwarding component for routing purposes. Packets are sent back to the ingress forwarding component in order to maintain load balancing of the packet flow across multiple forwarding components.

Accordingly, the ingress forwarding component determines a next hop of a plurality of next hops to forward the serviced packet to. The ingress forwarding component then transmits this packet to a second forwarding component that interfaces with router 10D. This second forwarding component acts as an egress forwarding component for this packet, and may remove any internal packet headers, perform one or more operations on the packet's format, update the packet header, etc. The egress forwarding component can then forward the serviced packet to the determined next hop, router 10D in the example of FIG. 1 .

In this way, the technique can enhance cost savings by potentially avoiding service card updates to perform the routing. This technique may also facilitate reduced implementation complexity compared to the hashing of service card updates and in terms of service card updates. In addition, the technique can maintain load balancing across forwarding components as determined by upstream external routers according to WECMP by enabling the service card to discard a hash of a packet to pseudo-randomly identify the forwarding component acting as the ingress forwarding component for the packet . Again, although described with respect to WECMP, the technique may generally be performed with respect to any load balancing algorithm, such as those utilized in performing link aggregation, and other forms of multipath or multilink load balancing.

FIG. 2 is a block diagram illustrating router 10B of FIG. 1 in more detail. In the example of FIG. 2 , router 10B includes forwarding plane 30 , routing plane 32 , and service plane 34 . Forwarding plane 30 may be provided by dedicated forwarding integrated circuits, typically associated with high-end routing and forwarding components of network routers. US patent application 2008/0044181 titled MULTI-CHASSISROUTER WITH MULTIPLEXED OPTICAL INTERCONNECTS describes a multi-chassis router in which a multi-stage switching fabric, such as a 3-stage Clos switching fabric, is used as the high-end forwarding plane, to relay packets between the routing nodes of the multi-chassis router. The entire content of US Patent Application 2008/0044181 is incorporated herein by reference.

Router 10B may integrate routing plane 32 and service plane 34 in a manner that utilizes shared forwarding plane 30 . Forwarding plane 30 may represent a rich and dynamic shared forwarding plane, optionally distributed through a multi-chassis router. Furthermore, as noted above, forwarding plane 30 may be provided by a dedicated forwarding integrated circuit typically associated with high-end routing and forwarding components of a network router. Thus, routing plane 32 and forwarding plane 30 operate as high-end routers, and service plane 36 has been tightly integrated within router 10B (e.g., by way of service cards 36) to facilitate the use of forwarding components in a shared, collaborative manner. Plane 30. Further details of an example embodiment of router 10B can be found in U.S. Provisional Patent Application 61/054,692, filed May 20, 2008, entitled "STREAMLINED PACKET FORWARDING USING DYNAMIC FILTERSFOR ROUTING AND SECURITY IN A SHARED FORWARDING PLANE," It is incorporated herein by reference.

Routing plane 32 provides a routing engine 38 which is primarily responsible for maintaining a routing information base (RIB) 40 reflecting the current topology of the network and other network entities to which router 10B is connected. For example, routing engine 38 provides an operating environment for the execution of routing protocols 42, which communicate with peer routers and periodically update RIB 40 to accurately reflect the topology of the network and other network entities. Example protocols include routing and label switching protocols such as Border Gateway Protocol (BGP), Intermediate System-to-Intermediate System (ISIS) routing protocol, Resource Reservation Protocol (RSVP), Traffic Engineering for RSVP referred to as "RSVP-TE" ( TE) version, Interior Gateway Protocol (IGP), Link State Protocol, and Label Distribution Protocol (LDP).

Routing engine 38 may receive this routing information via protocol 42 and update or otherwise maintain RIB 40 to reflect the current topology of network 6 . This topology can accommodate multiple different paths through the network to reach any given destination device. In the example of FIG. 1, two paths are shown from source device 12 to destination device 14, which are labeled paths 16A, 16B. In some examples, routing engine 38 may choose one of two paths to reach destination device 14 .

Administrator 45 may interface with routing engine 38 via a user interface (UI) module 46 , which may represent a module through which a user or provisioning system may interface with routing engine 38 . For example, UI module 46 may include a command line interface (CLI) or a graphical user interface (GUI), which may accept input in the form of commands and/or scripts. Administrator 45 may interface with UI module 46 to configure various components of router 10B, including routing engine 38 . Once configured, routing engine 38 may then decompose RIB 40 to generate forwarding information. Routing engine 38 may then interface with forwarding plane 30 to install this forwarding information into forwarding information base (FIB) 48 .

Forwarding component 50A maintains FIB 48 that associates network destinations with specific next hops and corresponding interface ports of output interface cards of router 10B. Routing engine 38 may generate FIB 48 in the form of a radix tree having leaf nodes representing destinations within the network. US Patent 7,184,437 provides details on an exemplary embodiment of a router utilizing radix trees for route resolution, the contents of which are incorporated herein by reference in its entirety.

When forwarding a packet, forwarding component 50A traverses the radix tree to leaf nodes based on the information within the packet's header to ultimately select the next hop and output interface to which to forward the packet. Based on this selection, the forwarding component can output the packet directly to the output interface, or in the case of a multi-stage switch fabric of a high-end router, the forwarding component can forward the packet to a subsequent stage for switching to the appropriate output interface.

Service plane 34 represents a logical or physical plane that provides one or more services in the form of service cards 36 . Service card 36 may represent a physical card configured to be inserted into router 10B and coupled to forwarding plane 30 and routing plane 32 via a backplane, switch fabric, or other communication medium. Typically, service cards 36 may comprise cards coupled directly to the switch fabric. Administrator 45 may interface with UI module 46 to interface with routing engine 38 to specify which packet flows are to undergo service processing by one or more service cards 36. After designating these flows, routing engine 38 may update RIB 40 to reflect that these flows will undergo service processing so that when FIB 48 is resolved, forwarding information may indicate that various flows will undergo service processing. Frequently, this forwarding information may specify these flows by specifying for these flows a next hop that directs packets of these flows to one of the service cards 36 (wherein this next hop may be referred to as an "internal next hop") Service processing is required. Additional next hops external to router 10B may be specified, where in this example the external next hop may specify to which of paths 16A, 16B the packet is to be forwarded. The internal next hop can be chained to the external next hop, where in this example router 10B can maintain two next hops (and possibly more) for any given flow.

The service cards 36 may each represent a card to which one or more services can be applied. Service card 36 may include control unit 50, which may represent one or more general-purpose processors (not shown in FIG. 1 ) that execute software instructions, such as stored to a non-transitory computer-readable medium (again, not shown in Figure 1), non-transitory computer-readable media such as storage devices (e.g., magnetic disk drives or optical drives), or memories (such as flash memory, random access memory, or RAM) that define software or computer programs ) or any other type of volatile or non-volatile memory that stores instructions to cause one or more processors to perform the techniques described herein. Alternatively, control unit 50 may represent dedicated hardware, such as one or more integrated circuits, one or more application specific integrated circuits (ASICs), one or more application specific special processors (ASSPs), one or more field programmable A gate array (FPGA), or any combination of the foregoing examples of one or more dedicated hardware, is used to perform the techniques described herein. In some instances, the control unit 50 may be referred to as a processor.

Control unit 50 may implement service engine 52, which may represent a module or unit that applies one or more services to packets, flows of packets, and/or sessions of packets (where a session refers to a flow from a source to a destination in conjunction with combination of flows from the same destination to the same source). Service engine 52 may perform any type of service, including those listed above. For purposes of illustration, it is assumed that service engine 52 implements a service that modifies, edits, or updates information in packets, which services are typically used in performing routing or otherwise making forwarding decisions. Example services that modify, edit or update this information may include NAT services and tunnel services.

In the example of FIG. 2 , forwarding component 50A receives packet 52 and acts as an ingress forwarding component, invoking flow control unit 54 . Flow control unit 54 represents a module that selectively directs packets to service plane 34 for processing. Flow control unit 54 may access FIB 48 to determine whether packet 52 is to be sent to an internal next hop, such as one of service cards 36 of service plane 34, or to an external next hop via another forwarding component that Acting as an egress forwarding component for the flow to which packet 52 corresponds, eg egress forwarding component 50B. Although referred to as ingress forwarding component 50A and egress forwarding component 50B, each of forwarding components 50A, 50B may be identical or similar to one another in terms of underlying hardware and/or logic. That is to say, the ingress and egress names of the forwarding components 50A, 50B only indicate that the forwarding component 50A acts as an ingress forwarding component for the packet flow corresponding to the packet 52, and the forwarding component 50B acts as an egress forwarding component for the packet flow corresponding to the packet 52 . Furthermore, forwarding plane 30 may include more than two forwarding components, wherein these additional forwarding components are not shown in the example of FIG. 2 for ease of illustration.

Regardless, flow control unit 54 may determine that packet 52 is to be transmitted to service card 36 . In response to determining that packet 52 is to be transmitted to service card 36 so that service card 36 can apply the service to packet 52, flow control unit 54 of ingress forwarding component 50A may append an internal service packet header (which may also be referred to as a "service cookie"). Flow control unit 54 may specify this inner service packet header to include a field that stores an entry identifier that identifies forwarding component 50A. Flow control unit 54 may append this inner service packet header to packet 52 to generate updated packet 56 . Flow control unit 54 may then redirect packet 52 to service card 36 of service plane 34 . Service card 36 may receive this packet, remove the inner service packet header, and parse the entry identifier from the inner service packet header. The control unit 50 of the service card 36 may then invoke the service engine 52 , which applies the service to the updated packet 56 , generating a serviced packet 58 . The service packet 58 is assumed to differ from the packet 52 in that at least one aspect of the service packet 58 used when making forwarding decisions or performing path selection differs from the packet 52, such as at least one of the five-tuples of the served packet 58 aspect differs from the quintuple of grouping 52). In this regard, service card 36 applies the service to updated packet 56 to generate serviced packet 58 such that the five-tuple of serviced packet 58 is different from the five-tuple of updated packet 52 .

Service card 36 may then transmit the serviced packet 58 back to flow control unit 54 using the ingress identifier previously parsed from the internal service packet header in order to maintain load balancing of the packet flow across the forwarding components of router 10B. That is, the service card 36 may actively identify one of the forwarding components 50A, 50B that originally received the packet 52 (and For ease of illustration, any other forwarding components are not shown in the example of FIG. 2). As a result, the service card 36 transmits the serviced packet 58 to the ingress forwarding component 50A identified by the ingress identifier without applying a hash function to at least a portion of the serviced packet 58 to identify the ingress forwarding component 50A, and /or do not determine a next hop to which to forward the served packet 58 . In addition, service card 36 transmits serviced packet 58 to ingress forwarding component 50A such that ingress forwarding component 50A receives the packet as if the packet had been associated by ingress forwarding component 50A via an ingress forwarding component 50A coupled to another network device. interface (not shown in the example of FIG. 2 ), rather than via the switch fabric coupling service card 36 to ingress forwarding component 50A. By selecting the ingress forwarding component 50A, the service card 36 maintains load balancing of the packet flow across the link/forwarding component (of the receiving router) determined by the upstream router according to WECMP.

Flow control unit 54 receives this served packet 58 and uses the 5-tuple of service packet 58 to access FIB 48 in order to retrieve the entry specifying the next hop for the flow to which service packet 58 corresponds. In other words, flow control unit 54 determines the next hop to which to forward served packet 58 based on the 5-tuple of served packet 58 . Assuming that flow control unit 54 identifies the next hop that involves forwarding a serviced packet 58 via the interface associated with egress forwarding component 50B, flow control unit 54 forwards this packet 58 to egress forwarding component 50B, which in turn, Egress forwarding component 50B forwards packet 58 to the next hop.

FIG. 3 is a block diagram illustrating the logical flow of packets through router 10B of FIG. 1, according to the techniques described in this disclosure. As shown in the example of FIG. 2 , the technique will be described with respect to ingress forwarding component 50A, egress forwarding component 50B, and service card 36 of router 10B.

In the example of FIG. 3 , ingress forwarding component 50A includes an interface card (IFC) 70 having a network interface 72 and a packet forwarding engine (PFE) 74 . The PFE 74 includes a flow control unit 54 (shown as "FCU 54 " in the example of FIG. 3 ). Egress forwarding component 50B also includes IFC 76 having interface 78 and PFE 80 . PFE 80 also includes FCU 82 which may be similar to FCU 54 .

As further shown in the example of FIG. 3 , an inbound packet 52 is received from one of the source devices 12 via the network interface 72 . FCU 54 of PFE 74 performs a routing lookup on inbound packet 82 and determines that the packet must be sent through switch fabric 84 to service card 36 . That is, FCU 54 performs a lookup in FIB 48 (shown in the example of FIG. 2, but not shown in the example of FIG. 3) to determine internal next-hop data that identifies service card 36 as a packet The egress interface to which it must send. After having been serviced by service card 36, to reswitch packets back to ingress forwarding component 50A, FCU 54 appends a service cookie that includes a field specifying an ingress identifier 88 that identifies ingress forwarding component 50A. PFE 74 then places this updated version of packet 52 (which may be referred to as updated packet 56 ) within buffer 86 to be directed through switch fabric 52A to service card 36 .

Control unit 50 of service card 36 receives updated packet 56 from switch fabric 84 and removes the service cookie, extracting ingress identifier 88 (shown as "ING ID88" in the example of FIG. 3 ) from updated packet 56 . Control unit 50 stores packet 56 to buffer 90 and invokes service engine 36 , which applies the service to updated packet 56 to generate serviced packet 58 . Control unit 50 places served packet 58 in packet buffer 92 . Control unit 50 may then use ingress identifier 88 to send serviced packet 58 such that PFE 74 receives serviced packet 58 as if the packet were received from an external network device terminating at PFE 74 . In some examples, ingress forwarding component 50A may include a tunneling packet interface card (PIC) that ingress forwarding component 50A may use to receive serviced packets that have been serviced by service card 36 (which from the perspective of PFE 74 will appear as outbound packet) to send the packet back to the PFE 74, where the tunneled packet has a payload encapsulating the fully formed packet destined for the interface 76. More information on the use of this tunnel PIC to enable ingress processing of what would otherwise be considered outbound packets can be found in the U.S. Found in Patent Application Serial No. 12/618,536, the entire contents of which are hereby incorporated by reference in their entirety.

In any case, as noted above, the PFE 74 may receive the packet 58 from the tunnel PIC as an inbound packet, ie, a packet on the network-facing inbound side of the PFE, as if it were received by a router from an external tunnel. The PFE 74 remove function may remove the tunnel cookie from the packet, and the FCU 54 performs a route lookup on this "inbound" packet 58, and determines that the packet must be sent through the switch fabric 84 to the associated egress forwarding component 50B of the network interface 76. PFE80. That is, the forwarding information accessed by FCU 54 maps keyed information within packet 58, such as the quintuple of packet 58, to next-hop data that identifies network interface 76 as the destination to which packet 58 is to be sent. export interface. As a result, PFE 74 places packet 58 within buffer 86 to be directed through switch fabric 84 to PFE 80 . PFE 80 receives packet 58 from switch fabric 84 as an outbound packet and places this outbound packet 58 in buffer 96 for output via egress interface 76 . IFC 76 then outputs packet 58 via interface 78 to its intended destination.

FIG. 4 is a block diagram illustrating an example service cookie 100 that is used to specify an entry identifier in accordance with the techniques described in this disclosure. In the example of FIG. 4, the service cookie 100 includes a number of fields, including a service type field (shown as "SVC TYPE"), an IP field (shown as "I"), an unused field (shown as "S") ), control field (shown as "C"), sequence field (shown as "N"), length field (shown as "LEN"), version field (shown as "VER"), match field, hash Column present field (shown as "H"), exit information field (shown as "E"), application identifier present field (shown as "A"), unused field (shown as "S") , Protocol field (shown as "PROTO"), Forwarding Class field (shown as "FC"), Drop Priority field (shown as "DP"), Send to Routing Engine (RE) field (shown as " R"), direction field (shown as "DIR"), new JFM cookie field (shown as "W"), IIF field, service identifier field, IF field, MID field, egress token field, and ingress Identifier field 102 . Each of the various fields specifies information used by the service card 36 to apply the appropriate service.

The entry identifier field 102 may include a Type Length Value (TLV) field that includes subfields to specify the type and length of information specified in a value sub-field. Alternatively, the entry identifier field 102 may be used to specify a set of entry identifiers or a defined length. The service cookie 100 above is a column of numbers from 31 (on the left) to 0 on the right, reflecting the number of bits used to specify each field. These bit notations are provided for example purposes, and service cookie 100 may include more or fewer bits, and each field specified in service cookie 100 may include more or fewer bits than shown in the example of FIG. bits.

5 is a flowchart illustrating example operation of a network device, such as router 10B shown in the examples of FIGS. 1-3 , in performing the service post-application load balancing techniques described in this disclosure. Although described with respect to a specific device, router 10B in the example of FIG. Any type of network device to perform both balancing and servicing.

Initially, forwarding component 50A (shown in the example of FIGS. 2 and 3 ) receives packet 52 ( 110 ), and acts as an ingress forwarding component, invoking flow control unit 54 . Flow control unit 54 may access FIB 48 to determine whether packet 52 is to be sent to an internal next hop, e.g., one of service cards 36 of service plane 34, or to an internal next hop via another forwarding component that forwards The component acts as an egress forwarding component for the flow to which packet 52 corresponds, eg egress forwarding component 50B. In this sense, flow control unit 54 may determine whether a service is to be applied to packet 52 (112). In other words, flow control unit 54 may determine that packet 52 is to be transmitted to service card 36 .

In response to determining that a service is to be applied to packet 52 ("Yes" 114), flow control unit 54 of ingress forwarding component 50A may generate an inner service packet header (which may also be referred to as a "service cookie" and with respect to described in more detail in the example of FIG. 4 ), and append this service cookie to packet 52 ( 116 , 118 ). Flow control unit 54 may then redirect or otherwise transmit updated packet 56 to service card 36 of service plane 34 via switch fabric 84 (shown in the example of FIG. 3 ) ( 120 ). The service card 36 may receive this packet, remove the inner service packet header, and parse the entry identifier from the inner service packet header. Control unit 50 of service card 36 may then invoke service engine 52, which applies the service to updated packet 56, generating serviced packet 58 (122). Service packets 58 are assumed to differ from packet 52 in that at least one aspect of service packet 58 is used when making forwarding decisions or performing routing five-tuple in packet 52). In this regard, service card 36 applies the service to updated packet 56 to generate serviced packet 58 such that the five-tuple of serviced packet 58 is different from the five-tuple of updated packet 52 .

The service card 36 may then transmit the serviced packet 58 via the switch fabric 84 back to the flow control unit 54 using the ingress identifier previously parsed from the internal service packet header to maintain, again across the forwarding component (124) Load balancing. That is, the service card 36 may actively identify one of the forwarding components 50A, 50B that originally received the packet 52 (and not shown for ease of illustration) acting as a so-called ingress forwarding component for the flow to which the packet 52 corresponds. any other forwarding components shown in the example of 2). As a result, the service card 36 transmits the serviced packet 58 to the ingress forwarding component 50A identified by the ingress identifier without applying a hash function to at least a portion of the serviced packet 58 to identify the ingress forwarding component 50A, and /or do not determine a next hop to which to forward the served packet 58 . In addition, service card 36 transmits serviced packet 58 to ingress forwarding component 50A such that ingress forwarding component 50A receives the packet as if it had been via an interface (not shown) associated with ingress forwarding component 50A coupled to another network device. shown in the example of FIG. 2 ) is received by ingress forwarding component 50A, rather than via the switch fabric coupling service card 36 to ingress forwarding component 50A.

The flow control unit 54 receives this served packet 58 and uses the 5-tuple of the service packet 58 to access the FIB 48 in order to retrieve an entry specifying the next hop for the flow to which the service packet 58 corresponds. In other words, flow control unit 54 determines a next hop to which to forward served packet 58 based on the 5-tuple of served packet 58 ( 126 ). If flow control unit 54 initially determines that the service will not be applied to packet 52 ("NO" 114), flow control unit 54 then determines the next hop for packet 52 in the same, if not substantially similar, manner. Regardless, flow control unit 54 uses FIB 48 to determine the next hop of the plurality of next hops. Assuming that flow control unit 54 identifies the next hop involved in forwarding serviced packet 58 via the interface associated with egress forwarding component 50B, flow control unit 54 forwards this packet 58 to egress forwarding component 50B, which in turn Packet 58 is forwarded to the next hop (128, 130).

6 is a block diagram illustrating an example network system 140 that performs the service post-application load balancing techniques described in this disclosure in the context of an aggregated bundle of two or more links. In the example of FIG. 6 , network system 140 includes public network 142 , service provider network 144 , and a plurality of subscriber networks 146A- 146N ("subscriber networks 146"). Although shown as including public network 142, service provider network 144, and subscriber network 146, network system 140 is but one example of the type of network system in which the techniques of this disclosure may be implemented. Although not shown in the example of FIG. 1 , network system 140 may include additional service provider networks, subscriber networks, and other types of networks, such as access networks, private networks, or generally employed to integrate one or more service Any other type of network (such as data services, Internet Protocol Television (IPTV) services, Voice over Internet Protocol (VoIP) services, video telephony services, or any other type of device) delivered to the subscriber network.

Public network 142 represents a network generally publicly accessible by any network-capable device with a network connection. The public network 142 may represent a network commonly referred to as the Internet, which refers to the public Layer 3 (L3) packet-switched network (where references to layers followed by numbers in this disclosure refer to the network in the Open Systems Interconnection ( corresponding layer in the OSI) model). Although not shown in the example of FIG. 1 , public network 142 generally includes a collection of interconnected network devices, to name a few by way of example, such as data servers, application servers, print servers, laptops, desktops, workstations, cellular Phones (including so-called "smart phones"), routers, switches, and hubs. Typically, although publicly available, the public network 142 is only accessible by network-capable devices with an active network connection, where such network connection is usually provided by a service provider network, such as in the form typically referred to as "data services" The service provider network 144 of .

Service provider network 144 represents one or more networks owned and operated by a service provider (which is typically a private entity) that provides one or more networks for consumption by a subscriber network, such as subscriber network 146 multiple services. Service provider network 144 is typically an L3 packet-switched network that provides L3 connectivity between public network 142 and subscriber network 146 . Often, the L3 connectivity provided by the service provider network 144 is sold as a data service or Internet service, and subscribers can subscribe to the data service. Recently, services provided from L3 packet-switched networks of service providers, such as telephony services or television services, are provided via different types of networks via service providers in the form of VoIP, Video on Demand (VoD) and IPTV respectively. L3 packet switching network to provide. As a result, service provider network 144 may offer a service referred to as "triple play" that includes each of data, voice, and television services over an L3 packet-switched network. Thus, service provider network 144 may represent an L3 packet-switched network that provides data, voice, television, and any other type of service for purchase by subscribers and subsequent consumption by subscriber network 146 .

Subscriber networks 146 each represent a network owned and operated by one or more subscribers to the services offered by service provider network 144 . Although not shown in the example of FIG. 1 for purposes of ease of illustration, subscriber networks 146 may each include one or more network-enabled devices, such as network-enabled printers, servers, laptops, desktops, Cellular phones (including smart phones), tablet or slate computers, notebooks, personal media players, game controllers, network-capable high-resolution disc players (such as Blu-ray disc players), digital video disc playback browsers, Internet-ready televisions, and e-reading devices.

A subscriber who owns and operates subscriber network 146 may subscribe to one or more services from a service provider who owns and operates service provider network 144, where such subscriber agreement generally indicates a level of service, quality of service, or category of service, service Providers generally agree on the level of service, quality of service, or category of service to provide one or more services. For example, one of the subscribers who owns and operates a corresponding one of the subscriber networks 146 may subscribe to a data service of a particular bandwidth, such as 10 megabits per second (Mbp), typically at a rate below In the class of service for the rate at which the service provider agrees to provide a less delay tolerant service, such as IPTV or VoIP. In some instances, a service provider may agree to provide all services to subscribers subscribed in a given class of service. Whether on an individual service basis or on a subscriber basis, a service provider generally agrees to provide a service to any given one of its subscribers according to an agreed service category, whether on an individual service basis or on a subscriber basis.

To provide these services according to the agreed service class or classes, the network equipment of the service provider network 144 that forwards traffic corresponding to these services implements a scheduling algorithm to schedule the subscriber traffic for delivery of the traffic Passed downstream (meaning from public network 142 to subscriber network 146 ) to subscriber network 146 in a manner to satisfy one or more classes of service associated with the subscriber. These scheduling algorithms may include Weighted Fair Queuing (WFQ) algorithms, however, WFQ algorithms are generally difficult to implement because it requires a large amount of computation to implement WFQ correctly. Accordingly, scheduling algorithms may include approximate WFQ algorithms, such as Weighted Round Robin (WRR) scheduling algorithms and Deficit Round Robin (DRR) scheduling algorithms. Alternatively, the scheduling algorithm may include the scheduling algorithm set forth in U.S. Patent No. 7,606,154, entitled "Fair Bandwidth Allocation Based on Configurable Service Classes," filed April 1, 2004, as set forth herein in its entirety through This reference is hereby incorporated. These scheduling algorithms seek to schedule traffic in such a way that bandwidth is fairly allocated to each data flow, so that the agreement of the class of service can be satisfied while also meeting any delay requirements, which may also form part of the class of service.

As further shown in the example of FIG. 6, service provider network 144 includes an exemplary network device shown as "router 148" and another network device shown as "access device 150." Router 148 represents any network device that routes or otherwise forwards traffic upstream from subscriber network 146 or downstream from subscriber network 146 . Router 148 typically represents an L3 packet-switching device operating at L3 to receive routing information describing the current topology of service provider network 144 . Router 148 then processes this routing information to route through the topology representation of service provider network 144 to all available destinations to generate forwarding information. In other words, router 148 reduces these paths to so-called "next hops," which identify which of its interface traffic is to be forwarded to a particular destination, where the forwarding information includes This list of next hops. Router 148 then installs this forwarding information in the forwarding plane of router 148, whereupon the forwarding plane forwards received traffic according to the forwarding information in the manner described in more detail above.

Access device 150 represents a network device that facilitates access of subscriber network 146 to service provider network 144 . Examples of access device 150 include Digital Subscriber Line Access Multiplexers (DSLAMs) and Cable Modem Termination Systems (CMTS). Typically, access device 150 aggregates upstream traffic from subscriber networks 146 to public network 142 and de-aggregates (or demultiplexes) aggregated downstream traffic from public network 142 to individual subscriber networks 146 Downstream business volume. In some examples, access device 150 may replicate some types of downstream traffic (eg, broadcast and multicast traffic) and pass this replicated traffic to subscriber device 146 .

Frequently, service providers employ a technique referred to as "bundling" to interconnect routers and access nodes via two or more links. Example aggregated bundles include aggregated Ethernet bundles, as defined by Multi-Link Segment Aggregation in IEEE 802.3ad, aggregated Ethernet bundles may be configured and maintained using the Link Aggregation Control Protocol (LACP), Multi-Link Segment Aggregation The content of is incorporated herein by reference. Logically, these aggregated bundles appear as a single connection to routers and/or access nodes. Aggregated bundles offer many benefits. First, aggregation bundles can provide redundancy of connections between routers and access nodes. To illustrate, if one link of the aggregated bundle fails, routers and access nodes interconnected by the aggregated bundle may redirect traffic previously sent over that failed connection of the aggregated bundle to one of the active links of the aggregated bundle, Redundancy of connections is thus provided between routers and access nodes. Second, the use of aggregated bundles can provide increased network capacity (which is often measured in units of bandwidth) given that multiple links of an aggregated bundle can be employed to carry traffic rather than a single link. Third, aggregated bundles can improve bandwidth scalability, as an example, because a service provider can build an aggregated bundle with two links, and then incrementally increase the number of links in the aggregated bundle in response to increasing subscriber bandwidth demands . In this way, service providers can mitigate capital expenditures by providing only sufficient bandwidth to meet current subscriber bandwidth needs rather than anticipated future subscriber bandwidth needs. Further exemplary details of multi-chassis link aggregation are exemplified in US Patent Application 13162157, entitled "AVTIVE-ACTIVE MULTI-HOMING WITH MULTI-CHASSIS PSEUDOWIRE LINKAGGREGATION," incorporated herein by reference.

Although aggregated bundles can provide for improved redundancy, bandwidth, and scalability, there is no need to schedule traffic to meet the class of service that a service provider has agreed to provide to its subscribers, while also taking advantage of the increased benefits offered by such aggregated bundles. Routers and/or access nodes may experience difficulties in bandwidth. To illustrate, consider a deployment of an aggregated bundle that assigns a (often, equal) portion of the subscriber's bandwidth to each link of the aggregated bundle, where the service provider has agreed in its class of service that the subscriber of bandwidth provided to subscribers. For example, if a subscriber has purchased 12Mpb service, the service provider can configure its routers to provide 1/3 of this 12Mpb over each of the three links of the aggregated bundle. However, this deployment of aggregated bundles is insufficient because subscriber traffic flows (where flows are usually identified by so-called five-tuples including source address, source port, destination address, destination port, and protocol) span Links may not be evenly distributed, resulting in incorrect application of service classes such as shaping (filtering), policing, caching, prioritization, etc. Also, some flows can consume more bandwidth than others, so the router can shape some flows so that they do not exceed the bandwidth cap of each link (that is, 4Mbps in the above example), even though the flow through the other two links The entire 4Mbps allocated for the corresponding subscribers on these links is not consumed.

Another bundle deployment defines links as active and standby at the link (or layer two of the OSI model) level such that all active traffic flows through the bundle use half of the bundle's links. This deployment can promote more accurate shaping than in the previously discussed deployments, while also providing link redundancy. However, this active/standby deployment limits the bandwidth to a single link, losing both the scalability aspect and the improved bandwidth aspect of using aggregated bundles.

In addition to these difficulties in exploiting the benefits offered by aggregated bundles while also ensuring accurate or at least reasonable service class scheduling, in many aggregated bundle deployments implementations that consider service applications of aggregated bundles may suffer from the above Router 10B in an equal-cost multipath environment describes many of the problems. That is, access node 150 may perform load balancing across links of aggregation bundle 152 (which may also be referred to as a "link aggregation group" or "LAG"). Application of a service may affect packets in such a way that forwarding decisions need to be made after or after application of the service. However, a service card of router 148 (which may be similar to service card 36 shown in the example of FIG. 2 ) may not be equipped or configured to handle packet forwarding decisions. Typically, these service cards apply a hash to the packet quintuple in the manner described above to pseudo-randomly redirect the packets back to one of the forwarding components.

However, these hash functions are only pseudo-random, and as a result the service card may transmit packets back to the forwarding components in a manner that does not actually result in an even distribution of load across the forwarding components. Furthermore, these service cards may not ensure that load balancing between two or more forwarding components according to the link aggregation protocol is maintained. Alternatively, the service cards may send these packets to forwarding components that are not even included in the aggregation group of links, further distorting any attempt at balancing load across these particular forwarding components.

Thus, router 148 may implement techniques contemplated in this disclosure to perform load balancing after serving applications. Router 148 may receive the packet with a first forwarding component of the plurality of forwarding components acting as an ingress forwarding component for a packet flow to which the received packet corresponds. This ingress forwarding component can determine that a service is to be applied to the packet in the manner described above. After identifying or otherwise determining that the service will be applied to the packet, in response to the determination that the service will be applied to the packet, the ingress forwarding component of router 148 may then update the packet to include an ingress identifier identifying the ingress forwarding component .

Once the packet is updated with the ingress identifier, the ingress forwarding component transmits the updated packet to the service card applying the service. The service card then applies the service to the updated packet to generate a serviced packet and transmits the serviced packet to the ingress forwarding component identified by the ingress identifier so as to maintain the load at load level at that time, and thus potentially avoid transmitting packets to forwarding components that may already be overloaded. Therefore, instead of performing a hash on the five-tuple of the packet to pseudo-randomly assign this packet to any given one of the forwarding components, the service card uses the ingress identifier to send the packet back to the ingress forwarding component , for the purpose of performing path selection.

The ingress forwarding component then determines a next hop of the plurality of next hops to forward the serviced packet to. The ingress forwarding component then transmits this packet to a second of the forwarding components interfacing with the selected next hop (e.g., to a neighboring device in the service providing network 144, which is not shown in the example of FIG. 6 middle). A second of the forwarding components acts as an egress forwarding component for this packet, and may remove any internal packet headers, perform one or more operations on the packet format, update the packet header, etc. The egress forwarding component can then forward the serviced packet to the determined next hop.

In this way, the technique can enhance cost savings by potentially avoiding service card updates to perform this routing. This technique may also promote reduced implementation complexity compared to both hashing of service cards and in updating of service cards. Additionally, the technique facilitates load balancing by enabling the service card to discard a hash of the packet to pseudo-randomly identify a forwarding component that will act as an ingress forwarding component for the packet, but is not configured to perform path selection according to a load balancing algorithm .

The techniques of this disclosure may be implemented in a wide variety of devices or apparatus, including networking equipment, an integrated circuit (IC), or a group of ICs (ie, a chipset). Any components, modules or units have been described provided to emphasize functional aspects and do not necessarily need to be realized by different hardware units. The techniques described herein may also be implemented in hardware or any combination of hardware and software and/or firmware. Any features described as modules, units or components may be implemented together in an integrated logic device or separately as discrete but interoperable logic devices. In some cases, various features may be implemented as an integrated circuit device, such as an integrated circuit chip or chipset.

If implemented in software, the techniques may be implemented at least in part by a computer-readable storage medium comprising instructions that, when executed in a processor, perform one or more of the methods described above. A computer readable storage medium may be a physical structure and may form part of a computer program product which may include packaging materials. In this sense, computer readable storage media may be non-transitory. The computer readable storage medium may include random access memory (RAM), such as synchronous dynamic random access memory (SDRAM), read only memory (ROM), nonvolatile random access memory (NVRAM), electrically erasable programmable Read-only memory (EEPROM), FLASH memory, magnetic or optical data storage media, etc.

The code or instructions may be executed by one or more processors, such as one or more digital signal processors (DSPs), general purpose microprocessors, application specific integrated circuits (ASICs), field programmable logic arrays (FPGAs), or others efficient integrated or discrete logic circuits. Thus, as used herein, the term "processor" may refer to any of the foregoing structure or any other structure suitable for implementation of the techniques described herein. Additionally, in some aspects, the functionality described herein may be provided within dedicated software modules or hardware modules configured for encoding and decoding, or incorporated into a combined video codec. Also, the technology can be fully implemented in one or more circuits or logic elements.

Various embodiments of the invention have been described. These and other implementations are within the scope of the following claims.

Claims (21)

1. a kind of method for computer network, including：

A packet is received with the first forwarding component being included in the multiple forwarding components in the network equipment, wherein the multiple First forwarding component of forwarding component serves as the entrance forwarding component for the stream of packets corresponding to the packet that is received；

Determine that a service will be applied to the packet with the entrance forwarding component；

The determination that will be applied to the packet is serviced in response to one, the packet is updated with the entrance forwarding component, with Portal identifier including recognizing the entrance forwarding component；

The packet for updating is transferred to using the service card of the service with the entrance forwarding component；

With the service card by the packet for being served by the renewal, to generate the packet through servicing；

The packet through servicing is transferred to the entrance recognized by the portal identifier with the service card to forward Component, in order to maintain the load balancing of stream of packets across the multiple forwarding component；

The next-hop in the multiple next-hops to its forwarding packet through servicing is determined with the entrance forwarding component；With And

The packet through servicing is forwarded to the second forwarding component in the multiple forwarding component identified next Jump, wherein second forwarding component in the multiple forwarding component served as dividing corresponding to the packet through servicing The outlet forwarding component of group stream.

2. method according to claim 1,

The stream of packets corresponding to wherein described received packet, by including source address, source port, destination-address, mesh Ground port and protocol the first five-tuple identification,

The stream of packets corresponding to the wherein described packet through servicing, by including source address, source port, destination-address, mesh Ground port and protocol the second five-tuple identification,

Wherein the packet being served by the renewal is included, with the service card by it is described be served by it is described more New packet with generate it is described through service packet so that second five-tuple be different from first five-tuple, and

Wherein determine that the next-hop in the multiple next-hop includes, determine to be forwarded to it based on second five-tuple The next-hop in the multiple next-hop of the packet through servicing, is grouped in order to distribute across the multiple next-hop Stream.

3. according to any one of claim 1 and 2 described method, wherein by the packet through servicing be transferred to it is described enter Mouthful forwarding component includes, the packet through servicing is transferred into the institute recognized by the portal identifier with the service card State entrance forwarding component, and without hash function is applied at least a portion of the packet through servicing with recognize it is described enter Mouth forwarding component.

4. according to any one of claim 1 and 2 described method, wherein by the packet through servicing be transferred to it is described enter Mouthful forwarding component includes, the packet through servicing is transferred into the institute recognized by the portal identifier with the service card Entrance forwarding component is stated, and the multiple next-hop to its forwarding packet through servicing is determined without the service card In the next-hop.

5. according to any one of claim 1 and 2 described method, wherein by the packet through servicing be transferred to it is described enter Mouthful forwarding component includes, the packet through servicing is transferred into the entrance forwarding component with the service card so that described Entrance forwarding component receives the packet, as the packet is via the entrance forwarding component, via be coupled to it is another The interface of the entrance forwarding component association of the individual network equipment and receive, rather than described via the service card is coupled to The switching fabric of entrance forwarding component.

6. according to any one of claim 1 and 2 described method, wherein the entrance forwarding component and the multiple forwarding Another forwarding component of component receives many according to equivalence via the adjacent network equipment from the adjacent network equipment Path ECMP algorithms or ECMP-WECMP algorithms of weighting send, dividing including the stream of packets corresponding to the packet The network equipment is coupled to the link of the adjacent network equipment across two or more for group stream, the ECMP or WECMP Load balancing is carried out to stream of packets.

7. according to any one of claim 1 and 2 described method, wherein the entrance forwarding component and the multiple forwarding Another forwarding component of component receives poly- according to link via the adjacent network equipment from the adjacent network equipment Hop algorithm the sends, stream of packets including the stream of packets corresponding to the packet, the link aggregation algorithm is polymerized two Or more link to form single virtual link, and the network equipment is coupled to the adjacent net across two or more The link pair stream of packets of network equipment carries out load balancing.

8. according to any one of claim 1 and 2 described method,

Wherein update the packet includes with including the portal identifier, and internal services packet header is attached to including specifying The packet of the field of the portal identifier, and

Wherein methods described is further included, before the packet through servicing is forwarded into the identified next-hop, Remove the internal services packet header.

9. a kind of network equipment, including：

Multiple forwarding components, wherein the first forwarding component in the multiple forwarding component receives a packet, and serve as use In the entrance forwarding component of the stream of packets corresponding to the packet for being received, determine that a service will be applied to the packet, ring The determination that will be applied to the packet is serviced described in Ying Yu, the packet is updated with including recognizing the entrance forwarding component Portal identifier, and the packet for updating is transferred to using the service card of the service；And

Service card, the service card is served by the packet to the renewal to generate the packet through servicing by described, and will The packet through servicing is transferred to the entrance forwarding component recognized by the portal identifier, in order to across described many Individual forwarding component maintains the load balancing of stream of packets,

Wherein described entrance forwarding component determines the next-hop in the multiple next-hops to its forwarding packet through servicing, with And

The second forwarding component in wherein the multiple forwarding component serves as the stream of packets corresponding to the service packet Outlet forwarding component, and the packet through servicing is forwarded to the identified next-hop.

10. the network equipment according to claim 9,

The stream of packets corresponding to wherein described received packet, by including source address, source port, destination-address, mesh Ground port and protocol the first five-tuple identification,

The stream of packets corresponding to the wherein described packet through servicing, by including source address, source port, destination-address, mesh Ground port and protocol the second five-tuple identification,

Wherein described service card is by following by the packet for being served by the renewal：Institute is served by by described State the packet of renewal to generate the packet through servicing so that second five-tuple is different from first five-tuple, with And

Wherein described entrance forwarding component determines the next-hop in the multiple next-hop by following：Based on described Two five-tuples come determine to its forwarding it is described through service packet the multiple next-hop in the next-hop, in order to across The multiple next-hop distributes stream of packets.

11. according to any one of the claim 9 and 10 described network equipment, wherein the service card by following by institute State the packet through servicing and be transferred to the entrance forwarding component：The packet through servicing is transferred to by the portal identifier The entrance forwarding component for being recognized, and without by hash function be applied to it is described through service packet at least a portion with Recognize the entrance forwarding component.

12. according to any one of the claim 9 and 10 described network equipment, wherein the service card by following by institute State the packet through servicing and be transferred to the entrance forwarding component：The packet through servicing is transferred to by the portal identifier The entrance forwarding component for being recognized, and determine without the service card to described in its forwarding packet through servicing The next-hop in multiple next-hops.

13. according to any one of the claim 9 and 10 described network equipment, wherein the service card by following by institute State the packet through servicing and be transferred to the entrance forwarding component：The packet through servicing is transferred to the entrance forwarding group Part so that the entrance forwarding component receives the packet, as the packet is via the entrance forwarding component, via with It is coupled to the interface of the entrance forwarding component association of another network equipment and receives, rather than via by the service card It is coupled to the switching fabric of the entrance forwarding component.

14. according to any one of the claim 9 and 10 described network equipment, wherein the entrance forwarding component and described many Another forwarding component of individual forwarding component from the adjacent network equipment receive via the adjacent network equipment according to It is that equal cost multipath ECMP algorithms or ECMP-WECMP algorithms of weighting send, including the packet corresponding to the packet The network equipment is coupled to the adjacent network equipment by the stream of packets of stream, the ECMP or WECMP across two or more Link pair stream of packets carry out load balancing.

15. according to any one of the claim 9 and 10 described network equipment, wherein the entrance forwarding component and described many Another forwarding component of individual forwarding component from the adjacent network equipment receive via the adjacent network equipment according to Link aggregation algorithm the sends, stream of packets including the stream of packets corresponding to the packet, the link aggregation algorithm gathers Two or more links are closed to form single virtual link, and the network equipment is coupled to the phase across two or more The link pair stream of packets of the adjacent network equipment carries out load balancing.

16. according to any one of the claim 9 and 10 described network equipment,

First forwarding component in wherein the multiple forwarding component updates the packet by following with including described Portal identifier：Internal services packet header is attached to the packet of the field including specifying the portal identifier, with And

The packet through servicing is being forwarded to the institute by second forwarding component in wherein the multiple forwarding component Before the next-hop of determination, the internal services packet header is removed.

A kind of 17. service cards, during the service card is configured to be inserted into as the network equipment described in claim 9, And multiple forwarding components of the network equipment are coupled to, the service card includes：

Control unit, described in described control unit from the entrance forwarding component served as the stream of packets corresponding to the packet The first forwarding component in multiple forwarding components receives a packet, wherein the packet includes internal services packet header, institute Stating internal services packet header includes specifying the field of portal identifier, and the portal identifier recognizes the entrance forwarding group Part, and

Wherein described control unit performs service-Engine, and the service-Engine will be served by the packet for updating to generate through clothes The packet of business,

Wherein the packet through servicing further is transferred to the institute recognized by the portal identifier by described control unit Entrance forwarding component is stated, in order to maintain the load balancing of stream of packets across the multiple forwarding component.

18. service cards according to claim 17,

The stream of packets corresponding to wherein described received packet, by including source address, source port, destination-address, mesh Ground port and protocol the first five-tuple identification,

The stream of packets corresponding to the wherein described packet through servicing, by including source address, source port, destination-address, mesh Ground port and protocol the second five-tuple identification, and

Wherein when the packet for being served by the renewal by described, the service-Engine by it is described be served by it is described more New packet with generate it is described through service packet so that second five-tuple be different from first five-tuple.

19. according to any one of claim 17 and 18 described service card, wherein described control unit by described through service Packet be transferred to the entrance forwarding component recognized by the portal identifier, and be applied to institute without by hash function At least a portion of packet is stated to recognize the entrance forwarding component.

20. according to any one of claim 17 and 18 described service card, wherein described control unit by described through service Packet be transferred to the entrance forwarding component recognized by the portal identifier, and determine without the service card to Next-hop in multiple next-hops of its forwarding packet through servicing.

21. divide the service according to any one of claim 17 and 18 described service card, wherein described control unit Group is transferred to the entrance forwarding component so that the entrance forwarding component receives packet, as the packet is via described Entrance forwarding component, receives via the interface of the entrance forwarding component association for being coupled to another network equipment, without It is via the switching fabric that the service card is coupled to the entrance forwarding component.