Patent Description:
A computer network is a collection of interconnected computing devices that can exchange data and share resources. In a packet-based network, the computing devices communicate data by dividing the data into small blocks 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.

Certain devices (i.e., nodes), such as routers, maintain routing information that describes routes through the network. A "route" can generally be defined as a path between two locations on the network. Upon receiving an incoming packet, the router examines keying information within the packet to identify the destination for the packet. Based on the destination, the router forwards the packet in accordance with the routing information.

Packet-based networks increasingly utilize label switching protocols for traffic engineering and other purposes. Multi-protocol label switching (MPLS) is a mechanism used to engineer traffic patterns within Internet protocol (IP) networks according to the routing information maintained by the routers in the networks. By utilizing MPLS protocols, label switching routers (LSRs) can forward traffic along a particular path, i.e., a label switched path (LSP), through a network to a destination device using labels prepended to the traffic. An LSP defines a distinct path through the network to carry MPLS packets from the source device to a destination device.

Document <CIT> discloses a system receiving a packet at a router, and pushing a label onto a label stack. The label stack is associated with the packet. The system provides a forwarding record containing label bindings for the router, and transmits the forwarding record to a collector. A system receives a forwarding record from a router. The system compares a first record entry type of the forwarding record with a second record entry type of the forwarding record to determine the traffic flow in the network. The system then maps the traffic flow in the network, based on a result of the comparing.

<NPL>) discloses that load balancing is a powerful tool for engineering traffic across a network. This document suggests ways of improving load balancing across MPLS networks using the concept of "entropy labels". It defines the concept, describes why entropy labels are useful, enumerates properties of entropy labels that allow maximal benefit, and shows how they can be signaled and used for various applications.

Document <CIT> discloses a method and a network device for tagging network traffic flows. Specifically, the method and system disclosed entail the incorporation of static user-defined tag information, as well as dynamic screener-defined tag information, into flow tracking information exported from flow tracking-capable network devices to one or more flow collectors. Incorporation of the aforementioned tag information enhances the ability of the flow collector(s) to index, as well as retrieve, the flow tracking information. Through enhanced indexing and retrieval, analysis of the flow tracking information, by one or more flow analyzers, may also be possible.

Optional embodiments of the invention are described in the dependent claims.

In general, the disclosure describes techniques that enable end-to-end flow monitoring in a computer network using entropy labels. To illustrate by way of an example computer network, an MPLS network may perform label allocation involving load balancing decisions and assign an entropy label (e.g., a hash value) to ensure that the packet data of a same network flow is forwarded along the same path among a plurality of paths as outlined in <NPL>, which is hereby explicitly referred to (referred to herein as "RFC <NUM>"). For example, an ingress router may determine the network flow (e.g., the application to which the packet belongs) of an incoming packet, and captures the flow information in an entropy label. Transit routers may use the entropy label to perform load balancing to ensure packet data is load balanced on the same path across multiple paths.

In accordance with the techniques described herein, a network controller may employ the entropy label as an index for network flow information stored in a data structure (e.g., a database). Because the labels allocated in MPLS networks are unique, some techniques leverage that quality to use the entropy labels as keys to monitor and track specific network flows.

Some techniques described herein are implemented in one or more of a number of routers that forward packet data along the computer network. Each router may be configured to repurpose entropy labels for end-to-end network flow monitoring. For example, an ingress router may export key information for computing the entropy label, which enables the network controller to distinguish between network flows. When packet data having the entropy label is received, each router in the MPLS network may generate a flow record to include the entropy label (as a primary key) and any useful information associated with the flow. By doing so, each router may be triggered by the entropy label into exporting, to the network controller, their flow record using the entropy label as the record's index key. The network controller may collect (e.g., and coalesce) the flow records from each router and continue to use the same entropy label as the key for those flow records. The network controller may use the flow record associated with a given entropy label to detect failures in the network flow. For example, if the network flow is down, the network controller may identify the routers that previously exported the flow record having the entropy label and identify which of those routers did not currently export the flow record.

The present disclosure sets forth, in the following description, an improvement to the functioning of computer networks and the techniques described herein integrate that improvement into practical applications. The following description (e.g., including the following examples) disclose additional details for the network devices (e.g., routers) and the network controller and their repurposing of entropy labels for end-to-end flow monitoring. As described herein, the network controller benefits from enabling end-to-end flow monitoring by using entropy labels as index keys for identifying corresponding network flows. Moreover, network devices (e.g. routers including the transit routers) benefit from a reduction in packet processing tasks as the use of entropy labels eliminates the need for deep packet inspection to identify the network flows.

In one example network comprising a plurality of network devices, there is provided a network device according to claim <NUM>.

In another network comprising a plurality of network devices, there is provided a controller according to claim <NUM>.

<FIG> is a block diagram illustrating an example system <NUM> in which client device <NUM> sends data to server device <NUM> with end-to-end flow monitoring on a label-switched path (LSP) <NUM>. LSP <NUM> (which may be herein referred to a tunnel or LSP tunnel) is formed by routers <NUM>-<NUM>, in this example, although it should be understood that fewer or additional network devices (not shown in <FIG>) may form LSP <NUM>. In this example, routers <NUM>-<NUM> are label switching routers (LSRs) along LSP <NUM>. Routers <NUM>-<NUM> execute protocols for establishing paths, such as LSP <NUM>. Such protocols may include, for example, link distribution protocol (LDP) or resource reservation protocol with traffic engineering extensions (RSVP-TE). LDP is described by "<NPL>, which is hereby explicitly referred to in its entirety. RSVP-TE is described by "<NPL>, which is updated by "<NPL>, which are both hereby explicitly referred to in their respective entireties. In some examples, routers <NUM>-<NUM> may use segment routing techniques, such as by using a Source Packet Routing in Networking (SPRING) paradigm, that provides segment routing to advertise single or multi-hop LSPs. Segment routing is further described in <NPL>, while Segment Routing use cases are described in <NPL>, the entire contents of each of which are explicitly referred to herein. Further details regarding SPRING are found in (<NUM>) "<NPL>; (<NUM>) <NPL>; (<NUM>) "<NPL>, the entire contents of each of which is explicitly referred to by reference herein.

In general, packets directed along LSP <NUM> are encapsulated by one or more labels in a label stack, e.g., in accordance with Multi-Protocol Label Switching (MPLS). In this manner, to direct traffic along an LSP, a router along the LSP may use a label of the label stack of a received packet to determine the "next hop" for the packet, that is, the next network device to which to forward the packet. In addition, the router may pop one or more labels from the label stack and push a new label onto the label stack, which causes the next hop to direct the packet along the LSP.

Although LSP <NUM> of <FIG> is shown as corresponding to routers <NUM>-<NUM> in <FIG>, in some examples, an LSP may be implemented using various, different sets of routers (not shown), e.g., to achieve load balancing. Rather than directing all traffic of client device <NUM> along routers <NUM>-<NUM>, a load balancing algorithm, such as equal-cost multipath (ECMP) may be used to distribute the traffic among different sets of devices that, ultimately, achieve the result of directing all traffic from client device <NUM> to server device <NUM>.

In general, when determining which of the sets of devices to direct traffic along to reach server device <NUM> when using a load-balancing algorithm (e.g., a mathematical function), a routing device computes a hash of the label stack of packets of the traffic. Assuming that two or more client devices are using the same path, however, the label stack will be the same for each client device. Therefore, RFC <NUM> proposed adding an entropy label into the label stack. The entropy label may be distinct for a particular packet flow directed along LSP tunnel <NUM>, such that a hash performed on the label stack for each packet of the packet flow will be directed along the same set of devices for the LSP, which may avoid out-of-order delivery for packets of the packet flow, but still allow for load balancing of different flows from the same client device.

RFC <NUM> is directed to using entropy labels when load balancing traffic for a single LSP. That is, devices along a single LSP may use the entropy label, and the last or penultimate router of the LSP is expected to remove the entropy label before forwarding the packet beyond the LSP. However, this disclosure recognizes that entropy labels can be repurposed for end-to-end flow monitoring for the LSP.

Devices, systems, and techniques described herein repurpose entropy labels, for example, as an index for enabling end-to-end flow monitoring. The term "packet flow," "traffic flow," or simply "flow" refers to a set of packets originating from a particular source device and sent to a particular destination device. A single flow of packets, in either an upstream (sourced by client device <NUM>) or downstream (destined for one of client devices <NUM>) direction, may be identified by attributes of a packet header, referred to as <NUM>-tuple: <source network address, destination network address, source port, destination port, protocol>, for example. This <NUM>-tuple generally identifies a packet flow to which a received packet corresponds. An n-tuple refers to any n items drawn from the <NUM>-tuple. For example, a <NUM>-tuple for a packet may refer to the combination of <source network address, destination network address> or <source network address, source port>, or any other combination of attributes in the packet header. A common example of a flow is a TCP session. Other examples are a Layer <NUM> Tunneling Protocol (L2TP) session corresponding to a given broadband user or traffic within an ATM virtual circuit. Some example devices, systems, and techniques are implemented in one or more of a number of routers that forward the packet data along the computer network. Other examples are implemented in a controller for the computer network.

Conventional networks may define templates specifying an exporting format for different routers to use when exporting flow records to a network controller. When such a network implements passive flow monitoring and/or active flow monitoring, a router may monitor the traffic flow and export flow information in a format defined by the template to the network controller. For example, the router may typically generate a flow record having information about the following fields: source and destination IP address; total number of bytes and packets sent; start and end times of the data flow; source and destination port numbers; TCP flags; IP protocol and IP type of service; originating Autonomous System of source and destination address; source and destination address prefix mask lengths; next-hop router's IP address; and MPLS label(s).

In a conventional network, each router may index a flow record using a set of multiple hash keys defined by, for example, the above-mentioned <NUM>-tuple but, due to the number of the multiple keys, it may be computationally expensive to index the flow record. In addition, for a single flow, the controller may receive different sets of multiple keys from the different routers, convoluting the identification of flow record for that flow. Moreover, MPLS encapsulation may, in many cases, require a fairly deep inspection of packets (referred to as "deep packet inspection") to find these keys, which is a complex key-search mechanism requiring additional processing.

For tunneled flows (e.g., MPLS over Generic Routing Encapsulation (GRE)), transit routers are unable to export flow records with application identifiers. For segment routing where the LSP is partitioned into segments, when routers using slice segment IDs (SIDs) to identify egress routers of each segment, the same slice SIDs are not configured to identify an application corresponding to the flow. Some conventional techniques implement network probing where the controller may send probes to determine issues within routers in the MPLS network but are unable to determine which application is affected in performance. Even when the probes clone application packet headers, the probes cannot identify which flows correspond to a particular application.

Because the entropy label, which may be generated from one or more attributes of a packet header, directs the network device to load balance each packet of the network flow along a same sequence of routers, the same entropy label may be used to index the flow records of the network flow. As described herein, controller <NUM> benefits from enabling end-to-end flow monitoring by using entropy labels as index keys for identifying corresponding network flows. The techniques described herein may provide for less complex transit routers with reduced processing tasks, enabling scalability to higher forwarding rates, larger port density, lower power consumption, among other benefits and improvements.

For example, rather than exporting a flow record identified by multiple keys, transit routers may instead export a flow record including an entropy label associated with the packet flow to controller <NUM>. Not only do conventional transit routers use a considerable number of attributes to generate the flow record's index key, the conventional transit routers must inspect the packet data to some non-trivial degree. In contrast, for transit routers of a same or similar structure, the techniques described herein enable flow record generation and exportation without a non-trivial inspection. Instead of independently computing the flow record's index key using the same set of multiple keys used by the ingress router in the same LSP <NUM> or a different set of multiple keys, the transit routers export (as at least a portion of the flow record), for example, the packet's label stack (e.g., tunnel labels and/or application labels) with little or no processing of the packet data. The transit routers described herein are not required to independently compute a copy of the same entropy label on the packet's label stack and, in some examples, may rely on the entropy label in the label stack as an accurate index key for the packet's corresponding network flow.

Thus, routers <NUM>-<NUM> also benefit from the techniques described herein because there will be no reason to implement a complex key-search mechanism to identify a given packet flow and to export such information to controller <NUM>. For example, in response to receiving packet data including an entropy label, the router of routers <NUM>-<NUM> receiving the packet may be triggered by the entropy label into exporting, to controller <NUM>, its flow record using the entropy label as the record's index key. Moreover, an egress router may exhibit a higher edge-service velocity.

Controller <NUM> may leverage entropy labels for a simple and immediate identification process for incoming flow records. When controller <NUM> receives a flow record with an entropy label, controller <NUM> (in turn) benefits from the corresponding entropy label being the flow record's index key by using the entropy label to quickly identify other corresponding network flow information including other flow records (e.g., downstream flow records) exported by one or more of routers <NUM>-<NUM> of an end-to-end path (e.g., LSP <NUM>) in the computer network. Controller <NUM> may quickly access these records to generate and analyze network flow statistics and/or determine errors in the network flow or the end-to-end path for the packet. For example, if any of routers <NUM>-<NUM> (e.g., the transit router, PHP router, and/or egress router) does not provide the flow record associated with the network flow's given entropy label, controller <NUM> may determine that router to be down or to have an error. Controller <NUM> may further determine that the entire path (and possibly LSP <NUM> in its entirety) is down or has an error.

To illustrate by way of an example, at least two of routers <NUM>-<NUM> form an MPLS network that performs label allocation (which may or may not involve any load balancing decisions) employing an entropy label as an index for network flow information stored in a data structure (e.g., database).

Depending upon the role, routers in the MPLS network may perform operations that either differ from or add to conventional functionality for entropy labels (e.g., as outlined in RFC <NUM>). For instance, an ingress router (e.g., router <NUM>) communicates to controller <NUM> key information used to compute the entropy label, which enables controller <NUM> to distinguish between network flows. The key information specifies attributes for computing for the entropy label. For example, an entropy label may be generated based on attributes of a packet header, such as a <NUM>-tuple. In this manner, the controller <NUM> may use the entropy label to distinguish between different network flows and identify network flow records received from routers along the path corresponding to the same network flow.

When a router (e.g., transit router, penultimate router) receives the packet data including the entropy label, the entropy label functions as a trigger for the receiving router to generate a flow record to include, for example, the following: the entropy label (as a primary key to identify the flow record); a protocol, an outgoing interface, and information associated with the packet flow. Example information associated with the packet flow may include MPLS header information (e.g., labels including tunnel label, application-specific label, etc.) and other information in the label stack. The router then sends the flow record and the entropy label to controller <NUM>.

Controller <NUM> may advantageously leverage the entropy label to determine errors in the network flow and/or in any of routers <NUM>-<NUM>. Controller <NUM> may manage a database of flow records that routers <NUM>-<NUM> exported in response to receiving packets with entropy labels. For each exported flow record that is received, controller <NUM> may utilize the record's entropy label to arrange (e.g., index) that flow record in the database and/or identify (e.g., index) any related flow record within the database. Controller <NUM> may use the flow record's entropy label to identify other flow records and the routers that exported the flow records for a same network flow. It should be noted that controller <NUM> is able use the entropy label as a simple mechanism to quickly identify which network flow corresponds to a given flow record. However, if controller <NUM> stops receiving flow records for a particular network flow, controller <NUM> may generate data indicating that the particular network flow and/or one or more routers <NUM>-<NUM> may be offline and/or malfunctioning, for example, in response to determining that packets for the particular network flow did not reach a destined transit, PHP, and/or egress router in LSP <NUM>. Without consuming substantial resource capacities and/or capabilities (e.g., memory), controller <NUM> may determine errors in the network flow and/or in any of routers <NUM>-<NUM>.

Controller <NUM> detects a failure, for example, when an incoming flow record does not indicate a conversion from a layer <NUM> protocol to a layer <NUM> protocol (or simply a layer <NUM> protocol). While some flow record formats may utilize different words for a same attribute field, a number of flow record formats implement an outgoing protocol field. For such flow record formats, controller <NUM> identifies a failed network flow if the outgoing protocol field includes corrupted, erroneous, or null data. Consider an example where controller <NUM> receives, from an ingress router of LSP <NUM>, a flow record with an entropy label that identifies a particular flow and an outgoing protocol field indicating an conversion from an incoming layer <NUM> protocol (e.g., IP) to a layer <NUM> protocol (e.g., MPLS); processing circuitry within controller <NUM> is configured to expect, from a corresponding egress router, a flow record having the same entropy label and an outgoing protocol of the incoming layer <NUM> protocol to any layer <NUM> protocol (e.g., IP or another protocol). If, however, controller <NUM> receives a flow record with the same entropy label but without the expected outgoing protocol, then controller <NUM> determines the particular flow is broken. By including the entropy label in the flow record (e.g., as an index key), the techniques described herein confer controller <NUM> with visibility into a given flow's path through routers <NUM>-<NUM> of LSP <NUM>. Controller <NUM> may arrange flow records in a flow record database according to the entropy label and by doing so, may reconstruct the given flow's (partial) path starting at an ingress router. Narrowing down routers <NUM>-<NUM> to a last router (e.g., an egress router such as router <NUM>) to process packets for that given flow enables controller <NUM> to quickly identify certain noteworthy details at the moment of failure. Controller <NUM> may determine that the failure resulted from errors (e.g., mechanical errors) on an outgoing interface (e.g., a media interface, such as Asynchronous Transfer Mode (ATM) or Ethernet) by identifying the outgoing interface from the flow record(s) of the last router and detecting these errors on that interface.

The devices, systems, and techniques described herein provide a solution where the entropy label is repurposed for not only identifying the application corresponding to the flow but also individual network flows.

<FIG> is a block diagram illustrating an example router <NUM> including a monitoring unit <NUM> configured according to the techniques of this disclosure. Router <NUM> may correspond to an ingress router, a transit router, a penultimate router, or an egress router, e.g., one of routers <NUM>, <NUM>, <NUM>, and <NUM> in <FIG>. In the example of <FIG>, router <NUM> includes interface cards 90A-90N (IFCs <NUM>), and control unit <NUM>. Control unit <NUM> includes packet forwarding engine (PFE) <NUM>, routing engine (RE) <NUM>, and monitoring unit <NUM>.

IFCs <NUM> receive data via respective inbound links 92A-92N (inbound links <NUM>) and send data via outbound links 94A-94N (outbound links <NUM>). Inbound links <NUM> and outbound links <NUM> in some examples form common, physical communication media for the IFCs, which operate in full duplex mode. That is, in some examples, each of IFCs <NUM> are coupled to respective communication media that can send and receive data substantially simultaneously. In other examples, inbound links <NUM> and outbound links <NUM> form separate physical media for respective IFCs <NUM>.

Control unit <NUM> includes processing hardware and, in some examples, software and/or firmware executed by the processing hardware. In various examples, control unit <NUM> and the various elements thereof, e.g., PFE <NUM> and RE <NUM>, are implemented in one or more processors, processing units, digital signal processors (DSPs), application specific integrated circuits (ASICs), field programmable gate arrays (FPGAs), or any combination thereof. When implemented in software or firmware, control unit <NUM> includes one or more processors or processing units for executing instructions for the software or firmware, as well as a computer-readable storage medium for storing the instructions. In some examples, elements of PFE <NUM> and RE <NUM> are implemented in discrete units or modules, while in other examples, PFE <NUM> and RE <NUM> are functionally integrated.

RE <NUM> includes instructions for one or more routing protocols <NUM>. Routing protocols <NUM> include any or all of interior gateway routing protocols such as open shortest path first (OSPF), intermediate system to intermediate system (IS-IS), routing information protocol (RIP), interior gateway routing protocol (IGRP), enhanced IGRP (EIGRP), and/or exterior gateway routing protocols, such as border gateway protocol (BGP). In general, interior gateway routing protocols are used to exchange routing information between routers of an autonomous system. Routing protocols <NUM> further include protocols related to network tunneling, such as MPLS, label distribution protocol (LDP), resource reservation protocol traffic engineering (RSVP-TE), or other protocols.

In general, RE <NUM> executes routing protocols <NUM> to determine routes between network devices, e.g., routes from router <NUM> to other network devices. Other routers coupled to router <NUM> via IFCs <NUM> advertise routes to router <NUM>. When router <NUM> receives a communication from another router that advertises a new route, RE <NUM> receives the communication and stores the new route in routing information <NUM> (also referred to as a routing information base). RE <NUM> also executes routing protocols <NUM> to prioritize routes from router <NUM> to a destination. That is, when routing information <NUM> includes information indicating that multiple routes exist to a common destination, RE <NUM> executes routing protocols <NUM> to select one of the routes to reach the destination.

The selected route to reach the destination generally includes an indication of a "next hop" along the route to reach the destination. This next hop typically corresponds to a network device, such as, for example, another router, switch, gateway, or other network device along the route to reach the destination. The next hop device is connected to router <NUM> via one of IFCs <NUM>. Accordingly, using the selected route to reach a destination, control unit <NUM> can determine the one of IFCs <NUM> connected to the next hop along the route to the destination and update forwarding information stored by PFE <NUM> to indicate the one of IFCs <NUM> to which to send packets destined for the destination.

More specifically, PFE <NUM> maintains forwarding information base (FIB) <NUM>. Then, in response to receiving information from routing engine <NUM>, PFE <NUM> updates FIB <NUM> to map a destination address to one of IFCs <NUM>, based on the next hop along the route to reach the destination address. FIB <NUM> also includes information indicating how to forward packets associated with a network tunnel, e.g., packets having one or more labels and/or packets to which to append one or more labels.

When router <NUM> operates as an ingress router for a tunnel (e.g., an LSP), router <NUM> receives a packet via one of inbound links <NUM> for one of IFCs <NUM>. In general, IFCs <NUM> are configured to send such a packet to forwarding engine <NUM>. Forwarding engine <NUM> determines the source device from which the packet was received based on the one of IFCs <NUM> that received the packet and the port of the one of IFCs <NUM> that received the packet. In some examples, forwarding engine <NUM> also determines the destination of the packet. In any case, forwarding engine <NUM> determines, using forwarding information <NUM>, that the packet is to be tunneled, and therefore, sends the packet to monitoring unit <NUM>. It should be understood that router <NUM> may also be configured to receive and process conventional network packets, e.g., packets not associated with a tunnel or packets not subject to load balancing decisions.

Monitoring unit <NUM> includes label data <NUM>, label handler <NUM>, entropy label handler <NUM>, and flow record data <NUM>. Label data <NUM> represents data for labels that can be appended to a received packet, as well as data for handling a packet having labels already appended. For example, when router <NUM> operates as an ingress router for a tunnel, label handler <NUM> receives the packet and determines a tunnel on which the packet is to be sent. Label handler <NUM> also determines, based on information received for the packet, a pair of edge routers for the packet and network layer services to be applied to the packet. Label handler <NUM> then determines, using label data <NUM>, labels representing the pair of edge routers (e.g., an application label such as a Virtual Private Network (VPN) label), the network layer services, and a tunnel label representative of the next hop along the tunnel.

Entropy label handler <NUM>, in accordance with the techniques of this disclosure, determines whether a label stack includes an entropy label identifier and an entropy label, removes the entropy label identifier and entropy label in certain circumstances, adds the entropy label identifier and entropy label in other cases, and moves the entropy label identifier and entropy label up or down in the label stack in still other cases. To determine appropriate label handling behavior, monitoring unit <NUM> determines whether router <NUM> is positioned between two routers of an end-to-end LSP or is an edge router of the end-to-end LSP.

To illustrate by way of a LSP tunnel as an example end-to-end path, when monitoring unit <NUM> determines that a packet of the LSP tunnel (e.g., LSP <NUM> of <FIG>) is received from a source device, that is received at an ingress router, and that is destined for a destination device, monitoring unit <NUM> determines that an entropy label should be added to a label stack for the packet. Thus, entropy label handler <NUM> computes the entropy label (e.g., from attributes of the packet header such as <NUM>-tuple) and adds an entropy label indicator and an entropy label to the label stack for the packet. This may occur after label handler <NUM> removes an incoming tunnel label, and before label handler <NUM> adds an outgoing tunnel label for the next hop. Label handler <NUM> may remove from or add to the packet's label stack an application label (if present) representative of a network service (e.g., a Virtual Private Network (VPN)) of router <NUM> and/or the destination device. Monitoring unit <NUM> generates a flow record for the packet's corresponding network flow and adds that flow record to flow record data <NUM> with an index key set to the entropy label or, as an alternative, with a value (e.g., a hash value) computed from one or more packet header attributes used for computing the entropy label.

In response to receiving the packet, monitoring unit <NUM> exports the attributes used to compute the entropy label and the flow record from flow record data <NUM> to the controller where the flow record is combined with other flow records with the entropy label corresponding to the same network flow. When subsequent packets arrive at router <NUM>, monitoring unit <NUM> repeats the generation and exportation of flow record data <NUM> to the controller. In some examples, monitoring unit <NUM> updates flow record data <NUM> after each packet and then, exports updated flow record data <NUM> to the controller.

As described herein, the controller leverages the entropy label in the exported flow record to identify the other flow records and quickly collate the disparate flow information that has been collected over time. In effect, the entropy label operates as an index key that facilitates end-to-end monitoring (e.g., of flow records) for the packet's corresponding network flow. Because the entropy label is unique, the index key for identifying the flow record is unique and therefore, configured to distinguish the flow record from other flow records in flow record data <NUM>. In addition, router <NUM> may communicate the flow record to a controller and in turn, the controller receives the flow record and uses the index key to identify the particular network flow. The controller may use the index key to store the flow record in an arrangement of other flow records for a plurality of network flows.

When monitoring unit <NUM> determines that a packet of the above LSP is received from an ingress router and is destined for another router in the LSP tunnel to a destination device (e.g., a transit router or an egress router), monitoring unit <NUM> determines that any entropy label in a label stack of the packet should be maintained and used to identify any flow record to be exported to the controller. When router <NUM> operates as a penultimate hop popping (PHP) router and an egress router is a next hop in the LSP, monitoring unit <NUM> configures router <NUM> to not remove the entropy label. This may occur after label handler <NUM> removes an incoming tunnel label for the packet, and before label handler <NUM> adds an outgoing tunnel label for the packet. Label data <NUM> indicates that the incoming tunnel label maps to the LSP and forwarding information <NUM> indicates a next hop, which is a next network device (e.g., router) in the LSP, corresponding to the outgoing tunnel label. Monitoring unit <NUM> generates a flow record for the packet's corresponding network flow and adds that flow record to flow record data <NUM>. Monitoring unit <NUM> also sends the flow record to the controller where the controller adds the flow record to an arrangement of flow records for each and every network flow. To facilitate end-to-end monitoring for a particular network flow that corresponds to the packet, monitoring unit <NUM> generates the flow record to include the entropy label. It should be noted that the monitoring unit <NUM> does not have to include the entropy label if the controller is configured to compute the entropy label (or another index key) from one or more attributes in the packet.

When monitoring unit <NUM> determines that a packet of the above LSP is received at an egress router, which may be entropy label capable or entropy label incapable, and is destined for a destination device (e.g., in another network which may not be entropy label capable), monitoring unit <NUM> determines that entropy labels in a label stack of the packet should be removed. Thus, entropy label handler <NUM> inspects the label stack of the packet to determine whether the label stack includes an entropy label indicator and an entropy label. If the label stack includes an entropy label indicator and an entropy label, entropy label handler <NUM> removes the entropy label indicator and entropy label. This may occur after label handler <NUM> removes an incoming tunnel label for the packet, and before label handler <NUM> adds an outgoing tunnel label for the packet. The egress router also receives a label on a top of the label stack and that label represents a network service (e.g., a network layer service, a transport layer service, and/or the like) for the destination device or a (destination) network (e.g., MPLS application, such as an IP Virtual Private Network (VPN), a MPLS Layer <NUM> VPN (L3VPN), or Virtual Private LAN Service (VPLS)) having the destination device. An example label may be a per-prefix L3VPN label that enables the packet to originate at a source device in a first network (e.g., segment), be received at an edge router (e.g., the ingress router) at a second network, and be directed to a destination device in a third network identified by the per-prefix L3VPN label.

In the above example, to facilitate end-to-end monitoring for a particular network flow that corresponds to the packet, monitoring unit <NUM> repurposes the entropy label for a particular network flow's flow record. Monitoring unit <NUM> may generate the flow record to include the entropy label and then, export the flow record to the controller where flow records for a plurality of network flows are processed and arranged into a database. By doing so, the controller may identify the particular network flow upon receiving the flow record. The entropy label operates as a unique identifier for the particular network flow such that the controller may distinguish flow records for the particular network flow amongst a plurality of flow records of other network flows. The controller may leverage the entropy label to build an index (e.g., a database) as an arrangement of flow records where the entropy label operates as an index key. The controller may store the flow record in the index and use flow record's entropy label to properly insert the flow record into the arrangement. Other portions of the flow record may specify information such as a number of packets in the particular network flow. Monitoring unit <NUM> may generate the entropy label based on one or more of various attributes describing packets of the particular network flow (e.g., packet header attributes including network addresses and port numbers for source and destination devices, outgoing interface, a protocol type, and/or the like). As an alternative, monitoring unit <NUM> computes a different value to operate as the index key for distinguishing the flow record from flow record of other network flows. Monitoring unit <NUM> may use one or more packet header attributes to generate the entropy label and one or more different packet header attributes to compute the value for the alternative index key. In turn, when the controller receives the flow record, the controller uses either the same set of attributes to compute the entropy label or the value to use as alternative the index key. The controller may repurpose the entropy label as described herein even if the entropy label is not being used for load balancing decisions (e.g., label-based load balancing).

<FIG> is a conceptual diagram illustrating end-to-end flow monitoring and flow record management by controller <NUM> of a network. Routers <NUM>, <NUM>, <NUM>, <NUM> comprise at least a portion of the network's routers. Each router in the network communicates flow records in response to receiving packet data corresponding to network flows.

Controller may be an SDN controller that enables granular visibility and control of IP/MPLS tunnels in large service provider and enterprise networks. Network operators can use controller <NUM> to optimize their network infrastructure through proactive monitoring, planning, and explicit routing of large traffic loads dynamically based on entropy label-based load balancing.

Assuming routers <NUM>, <NUM>, <NUM>, <NUM> form a tunnel (e.g., an LDP or intra-autonomous system tunnel), packet data for any network flow mapped to this tunnel is communicated along routers <NUM>, <NUM>, <NUM>, <NUM>. If label-based load balancing is employed, an entropy label may ensure the communication of the packet data along the same sequence of routers <NUM>, <NUM>, <NUM>, <NUM>. Initially, ingress Label Edge Router (LER) <NUM> receives the packet data and in response to determining that the packet data belongs to a new network flow, generates a flow record to include the entropy label and/or data indicating one or more attributes for computing the entropy label. Ingress LER <NUM> sends to controller <NUM> the data indicating the one or more attributes used for computing the entropy label to enable controller <NUM> to identify a particular flow based on the entropy label and to perform flow monitoring on end-to-end paths such as LSP <NUM> of <FIG>. Receiving the one or more attributes prompts controller <NUM> to register the one or more attributes as key information for a new network flow with Ingress LER <NUM>, an incoming/outgoing protocol, and an outgoing interface (e.g., an MPLS network). As described herein, the one or more attributes describe packets for the new network flow and may be stored in any packet header. To support the controller's flow monitoring operations, Ingress LER <NUM> sends the flow record with the entropy label and any other flow information.

To prepare an example packet for forwarding along the label switched path (or another example end-to end path), Ingress LER <NUM> may add, to a label stack of the packet data, the entropy label and at least one label (e.g., tunnel label) for forwarding the packet data along the tunnel. Then, Ingress LER <NUM> sends to a next hop identified by the label stack, which in this example is transit Label Switching Router (LSR) <NUM>. If Ingress LER <NUM> may employ a load balancing mechanism to calculate a hash value (e.g., an entropy label) of the packet data, including the one or more attributes located in the packet header, and determine a path for packets of the network flow based on the hash value. The entropy label may be based on the hash value and/or another value. Ingress LER <NUM> forwards the above packets to a device known as the next hop along the determined path.

In response to receiving the packet data including the entropy label, transit LSR <NUM> also generates a flow record that may include, in some examples, different data than other flow records. As such, the flow record from transit LSR <NUM> may be considered a copy or version of the flow record. Transit LSR <NUM> proceeds to send, to controller <NUM>, the flow record (e.g., transport labels, application-specific labels, outgoing interface, protocol, etc.) including the entropy label. In some examples, transit LSR <NUM> may also export additional information associated with the flow record such as the number of packets, number of bytes, etc. Similar, Penultimate Hop Popping (PHP) Router <NUM> receives the packet data and then, generates a copy or version of the flow record for export to controller <NUM>. In this example, PHP router <NUM> does not remove the entropy label and is configured to retain the entropy label on the label stack.

Finally, egress router <NUM> receives the packet data and then, generates a copy or version of the flow record for export to controller <NUM>. Egress router <NUM> removes the entropy label and uses the outgoing protocol (e.g., IP) and outgoing interface to forward the packet to the destination.

Although the packet of the network flow is forwarded from ingress LER <NUM> to egress router <NUM>, egress router <NUM> may propagate, in a reverse direction, various data. In accordance with a signaling protocol, egress router <NUM> may communicate to upstream routers a signaling message indicating a capability or a requirement at that router, and one example signaling message indicates whether or not egress router <NUM> is entropy label capable. Transit LSR <NUM> or PHP router <NUM> may also send signals upstream including the example signal indicating that transit LSR <NUM> or PHP router <NUM>, respectively, is entropy label capable or is entropy label incapable. Ingress LER <NUM> may communicate signals to the source device which may be in a same network (e.g., segment) or in a different network.

If egress router <NUM> is an egress of an LDP tunnel as an example of the above mentioned tunnel, egress router <NUM> may signal upstream labels (e.g., tunnel labels) representative of each hop in that LDP tunnel. Hence, PHP router <NUM> receives a set of labels including a label for each of ingress LER <NUM>, transit LSR <NUM>, PHP router <NUM>, and egress router <NUM> and before propagating to transit LSR <NUM> the set of labels, PHP router <NUM> removes the label for egress router <NUM> and retains it in available label data (e.g., label data <NUM>). Transit LSR <NUM>, in a similar fashion, retains a label for PHP router <NUM> and propagates upstream a label for itself to ingress LER <NUM>. If needed, ingress LER <NUM> may remove the label for transit LSR <NUM>. When a packet of the network flow arrives at a source device and is to be transmitted along the LDP tunnel, the source device identifies ingress LER <NUM> as a neighboring router and an ingress to an end-to-end path to the destination device.

When the packet along the LDP tunnel arrives, ingress LER <NUM> may add to the packet's label stack the entropy label and the label for Transit LSR <NUM> and then, send the packet further along the LDP tunnel. Similarly, when the packet along the LDP tunnel arrives at transit LSR <NUM>, that router may replace a label at top of the label stack with the label for a next ho, which may be another transit LSR <NUM> or PHP router <NUM>. When the packet along the LDP tunnel arrives at PHP router <NUM>, that router may replace a label at top of the label stack with the label for egress router <NUM>.

<FIG> is a conceptual diagram illustrating an example packet <NUM> that an ingress router <NUM> receives and modifies to add entropy label <NUM>. Ingress router <NUM> may represent an example implementation of router <NUM> of <FIG> and/or ingress LER <NUM> of <FIG>. Ingress router <NUM> may receive packet <NUM> from a source device. Alternatively, ingress router <NUM> may receive an encapsulated packet having packet <NUM> (e.g., as an inner packet) from either an entropy label capable segment or a non-entropy label capable segment of an end-to-end LSP.

In example packet <NUM>, packet data includes a packet header and payload of application data. Attributes with the packet data (e.g., from the packet header) may describe a network flow corresponding to packet <NUM> and an end-to-end path between a source device and a destination device. Ingress router <NUM> may generate entropy label <NUM> based on one or attributes within the packet data (e.g., the packet header) and then, send the attributes used to compute the entropy label <NUM> and a flow record identified by the entropy label <NUM> to controller <NUM> to facilitate end-to-end flow monitoring.

Ingress router <NUM> may add entropy label indicator <NUM> and entropy label <NUM> to packet data in packet <NUM> if ingress router <NUM> is entropy label capable. Based on forwarding information for the tunnel, ingress router <NUM> adds tunnel label <NUM>, which corresponds to a next hop in the tunnel, to label stack <NUM> of modified encapsulated packet <NUM>. Thus, label stack <NUM> includes tunnel label <NUM>. In some examples, tunnel label <NUM> is representative of the autonomous system encompassing ingress router <NUM> and between a source device and a destination device of example packet <NUM>. Within that same autonomous system, ingress router <NUM> and at least one other router may form a tunnel (e.g., an LDP tunnel) where each router may be assigned a representative tunnel label.

Thus, the encapsulated packet <NUM> is encapsulated by label stack <NUM>, which includes an entropy label indicator and an entropy label. As an option, ingress router, before adding entropy label indicator <NUM> and entropy label <NUM>, may add application label to represent a MPLS application (e.g., VPN) of the destination device.

In general, label-based load balancing involves selecting keys for a load-balancing function that selects a path for a (new) network flow and acceptable keys may be selected from packet data attributes (e.g., application-specific attributes, such as VPN-specific attributes) for the network flow; an example set of keys includes source and destination network addresses (e.g., IP addresses for IP packets), a protocol type, and (e.g., for TCP and UDP traffic) the source and destination port numbers. In one example, ingress router <NUM> uses the load balancing function to generate entropy label <NUM> from the example set of keys and then, repurpose entropy label <NUM> for end-to-end flow monitoring as describe herein.

Adding entropy label <NUM> ensures downstream transit routers forward packets belonging to the same network flow because, in effect entropy label <NUM> is mapped to a same path (e.g., a same exact sequence of routers across the network such as the LDP tunnel). Example device, systems, and techniques, as described in the present disclosure, leverage entropy label <NUM> to ensure that each downstream router receiving encapsulated packets generates flow record data using a same index key and to export the flow record to the controller. Some examples may use a copy of at least a portion of entropy label <NUM> while other examples may use another value (e.g., a hash value) based on entropy label <NUM> or based on one or more of the above mentioned example set of keys. Ingress router <NUM> may generate the index key from one or more attributes of the packet data attributes (e.g., application-specific attributes).

<FIG> is a conceptual diagram illustrating an example encapsulated packet <NUM> that router <NUM> received and forwarded to a next router. Router <NUM> may represent an example implementation of any of routers <NUM>, <NUM>, <NUM>, <NUM>, <NUM> of <FIG> and/or routers <NUM>, <NUM> of <FIG>. In some examples, router <NUM> receives encapsulated packet <NUM> from an ingress router (or previous hop transit router) and outputs modified encapsulated packet <NUM> to the next router, such as a transit router or an egress router of a same tunnel. In the example of <FIG>, encapsulated packet <NUM> includes packet <NUM> that is encapsulated by label stack <NUM>. Label stack <NUM> includes tunnel label <NUM>, entropy label indicator <NUM>, and entropy label <NUM>.

Based on an identification of a next hop in a tunnel corresponding to tunnel label <NUM>, router <NUM> removes tunnel label <NUM> from label stack <NUM> and adds tunnel label <NUM>, which is representative of the next hop, to produce modified encapsulated packet <NUM> with modified label stack <NUM>. In other examples, such as in segment routing, the router may pop off the outer label and forward the packet to the next label in the tunnel label stack. Assuming the next hop is entropy label capable, entropy label <NUM> ensures that the next hop transmits packet <NUM> along the above-mentioned tunnel. If the next hop is not entropy label capable, the next hop may transmit packet <NUM> along a different path, ignoring entropy label <NUM>, while still providing controller <NUM> with a flow record for the corresponding network flow for encapsulated packet <NUM>. The flow record may include an index key based on entropy label <NUM>. In either case, router <NUM> may operate as a transit/penultimate hop popping router and generate the flow record for exportation with the entropy label <NUM> to controller <NUM>.

<FIG> is a conceptual diagram illustrating an example encapsulated packet <NUM> that is received by egress router <NUM> of an end-to-end LSP and is to be output to a destination device of the LSP. Router <NUM> may represent an example implementation of router <NUM> of <FIG> and/or egress router <NUM> of <FIG>.

In this example, encapsulated packet <NUM> includes packet <NUM> and label stack <NUM>. Packet <NUM> may be known as an inner packet of encapsulated packet <NUM>. Label stack <NUM> includes tunnel label <NUM>, entropy label indicator <NUM>, and entropy label <NUM>. Egress router <NUM>, which may include components similar to those of router <NUM> illustrated in <FIG>, may modify (e.g., decapsulate) encapsulated packet <NUM> in accordance with the techniques of this disclosure.

Example encapsulated packet <NUM> may be received from a router within a same network and is to be output to the destination device of the LSP tunnel also within the same network. Hence, the LSP tunnel may be an intra-Autonomous System (AS) tunnel. Prior to delivering encapsulated packet <NUM> to the destination device, egress router <NUM> may modify (e.g., decapsulate) that packet by removing tunnel label <NUM>, entropy label indicator <NUM>, and entropy label <NUM> and then, send packet <NUM> based on the outgoing protocol and outgoing interface. By communicating the above modified packet data to the destination device (or another router in a second network), egress router <NUM> complies with the label-based load balancing scheme (per RFC <NUM>) and may prevent errors downstream.

To facilitate end-to-end monitoring of the network flow, egress router <NUM>, like other routers in same network, may be configured to export the flow record and entropy label <NUM> to controller <NUM>. In accordance with devices, systems, and techniques described herein, controller <NUM>, like egress router <NUM> and other routers in same network, generates an index key for the flow record using the same above-mentioned set of attributes that were used in computing entropy label <NUM>. Each router sends the controller a flow record having the same index key, allowing controller <NUM> to identify the flow record amongst flow records of other network flows.

It should be understood that additional labels may be included in label stack <NUM> that are not shown in <FIG>. Similarly, in the examples of <FIG> and <FIG> as discussed herein, the full label stack is not necessarily illustrated in the figures.

<FIG> is a flow diagram illustrating an example method for computing an entropy label to use as an index key for flow records corresponding to a same flow.

The method of <FIG> may be performed by any of routing network devices described above, which may be an ingress router, a transit router, or an egress router. For purposes of example, the method of <FIG> is described with respect to router <NUM> of <FIG>. The router <NUM> can be implemented using the features described below to fall within the scope of claim <NUM>.

Initially, router <NUM> receives packet data (or simply a packet) of a network flow (<NUM>). If router <NUM> operates as the ingress router, the packet data is received from a source device or an edge router in a different network, such as a non-entropy label capable (ELC) segment of an end-to-end LSP. If router <NUM> operates as the transit router or the egress router, router <NUM> may receive the packet data from another router in the same network, such as the ingress router or previous hop transit router.

Router <NUM> may then generate a flow record for a corresponding network flow of the packet data (<NUM>). When router <NUM> receives the packet data, router <NUM> may be triggered into determining that the packet data corresponds to a new network flow and generating a new flow record identified by an entropy label. Router <NUM> generates a flow record to include, for example, the following: the entropy label (as a primary key to identify the flow record); a protocol, an outgoing interface, and information associated with the packet flow. Example information associated with the packet flow may include MPLS header information (e.g., labels including tunnel label, application-specific label, etc.) and other information in the label stack.

Router <NUM> sends to a controller the flow record (<NUM>). If router <NUM> is an ingress router, router <NUM> may also send the attribute(s) used for computing the entropy label. In addition to the entropy label and the flow record, it is more important that the controller receives information identifying which attribute(s) (e.g., packet header attribute(s)) may be used for computing the entropy label and identifying the flow record. By doing so, the controller may distinguish the flow record for the packet data's network flow from flow records of other network flows.

Router <NUM> may then send the packet data to a next hop (<NUM>). Assuming router <NUM> implements label-based forwarding, router <NUM> may pop or remove a top label of a label stack in the packet data and using forwarding information, identify the next hop that maps to the top label. The next hop may be a network device along a same tunnel as router <NUM> and as such, may be assigned a tunnel label. In other examples, the next hop may be a network device that maps to a different tunnel than router <NUM> and assigned a corresponding tunnel label or to no tunnel at all and assigned a generic label, both of which map to the same next hop network device. Router <NUM> adds the appropriate label unless router <NUM> operates as the egress router in which instance router <NUM> does not add any label before sending the packet data to the next hop.

<FIG> is a flow diagram illustrating an example method executed by a controller in a network that provides end-to-end flow monitoring. For purposes of example, the method of <FIG> is described with respect to controller <NUM> of <FIG>.

Initially, controller <NUM> receives (e.g., from an ingress router) key information of a new network flow (<NUM>). In some examples, the key information operates as a set of hash keys for computing a new entropy label in accordance with label-based load balancing scheme (per RFC <NUM>). For example, controller <NUM> receives key information used to compute the entropy label from an ingress router of the network flow. Regardless of whether or not the entropy label is actually used in multi-pathing, controller <NUM> repurposes the entropy label for use in identifying flow records for the new network flow. Hence, the entropy label may be computed from key information including only one attribute or as many attributes specified by the label-based load balancing scheme (per RFC <NUM>).

Controller <NUM> receives flow records from routers in the network and uses the entropy label to distinguish the flow records of the new network flow (<NUM>). This is enabled by routers in the network generating flow records that include the entropy label corresponding to the new network flow. In some examples, the routers in the network may generate flow records by inserting, into a flow record template, a label stack from an incoming packet of the new network flow. If controller <NUM> suspects that the packet or the entropy label itself has been being compromised, controller <NUM> may use key information to verify the entropy label in the label stack. In other examples, the routers in the network may generate flow records without including the entropy label used for load balancing.

Controller <NUM> then updates a database (e.g., an index) to store the received flow records of the new network flow (<NUM>). Controller <NUM> may then proceed to generate flow statistics and/or monitor the network flow for any failures (<NUM>). Those skilled in related art may use flow statistics (e.g., NetFlow statistics) in various network management tasks. Flow statistics are useful for several applications such as Network Monitoring. Flow statistics can also be used to measure how application and policy changes affect flow traffic.

Therefore, from one perspective three has been described that in a network comprising a plurality of network devices, a network device can include processing circuitry configured to: receive packet data corresponding to a network flow originating at a first device, the packet data destined to a second device; generate an entropy label to add to a label stack of the packet data, wherein the entropy label is generated from one or more attributes corresponding to the network flow that originated at the first device and is destined to the second device; generate a flow record including the entropy label, wherein the entropy label identifies the network flow amongst a plurality of network flows in the network; and send, to a controller of the network, the flow record, wherein the controller identifies the flow record based on the entropy label corresponding to the network flow originating at the first device and is destined to the second device.

If implemented in hardware, this disclosure may be directed to an apparatus such a processor or an integrated circuit device, such as an integrated circuit chip or chipset. Alternatively, or additionally, if implemented in software or firmware, the techniques may be realized at least in part by a computer-readable data storage medium comprising instructions that, when executed, cause a processor to perform one or more of the methods described above. For example, the computer-readable data storage medium may store such instructions for execution by a processor.

A computer-readable medium may form part of a computer program product, which may include packaging materials. A computer-readable medium may comprise a computer data storage medium such as random access memory (RAM), read-only memory (ROM), non-volatile random access memory (NVRAM), electrically erasable programmable read-only memory (EEPROM), Flash memory, magnetic or optical data storage media, and the like. In some examples, an article of manufacture may comprise one or more computer-readable storage media. A computer readable medium may additionally or alternatively comprise a transmission medium such as a transient carrier wave or transmission protocol stream, and may be used to move instructions and/or data between components of a single computer system or to move instructions and/or data between separate computer systems.

In some examples, a computer-readable storage media may comprise non-transitory media. The term "non-transitory" may indicate that the storage medium is not embodied in a carrier wave or a propagated signal. In certain examples, a non-transitory storage medium may store data that can, over time, change (e.g., in RAM or cache).

The code or instructions may be software and/or firmware executed by processing circuitry including one or more processors, such as one or more digital signal processors (DSPs), general purpose microprocessors, application-specific integrated circuits (ASICs), field-programmable gate arrays (FPGAs), or other equivalent integrated or discrete logic circuitry. In addition, in some aspects, functionality described in this disclosure may be provided within software modules or hardware modules.

Various examples have been described. These and other examples are within the scope of the following claims.

Claim 1:
A network device in a network comprising a plurality of network devices, the network device comprising:
processing circuitry configured to:
receive (<NUM>) packet data corresponding to a network flow originating at a first device, the packet data destined to a second device;
generate an entropy label (<NUM>) to add to a label stack (<NUM>, <NUM>, <NUM>) of the packet data, wherein the entropy label is generated from one or more attributes corresponding to the network flow that originated at the first device and is destined to the second device;
generate (<NUM>) a flow record including the entropy label, wherein the entropy label identifies the network flow amongst a plurality of network flows in the network;
send (<NUM>), to a controller (<NUM>, <NUM>) of the network, the flow record, wherein the flow record is configured to enable the controller to identify the flow record based on the entropy label corresponding to the network flow originating at the first device and is destined to the second device; wherein the processing circuitry is further configured to send, to the controller of the network, the one or more attributes used to generate the entropy label.