Patent Description:
In some networks, a network congestion state, or flow control information, may be provided to a transmitter for determining when to throttle traffic. However, in other networks, the congestion or flow control information may be unavailable or impractical to provide for traffic shaping purposes. For example, in a mesh-based network with dozens or hundreds of clients accessing the mesh simultaneously, it may be impractical to provide feedback to a transmitter regarding the state of network congestion because the cost of detecting and distributing this information in the mesh may be too high, and the relevance of such information may not be assured (e.g., when the state of congestion in the network changes before the information can be utilized).

<CIT> describes a mobile computing device that supports cost-aware application components for operation over a metered network. A current basis for computing usage charges over one or more networks may be made available to the cost-aware application components through an application programming interface supported by an operating system service. That service may receive a policy for charging for data usage over a network and may also obtain information defining data usage for the mobile computing device. Based on this information, the service may determine a current basis for charging for data usage. With this information, the application component can determine a manner for executing network operations that involve data transmission over the network, such as deferring the operation or selecting an alternative network.

Further features and advantages of embodiments, as well as the structure and operation of various embodiments, are described in detail below with reference to the accompanying drawings. It is noted that the methods and systems are not limited to the specific embodiments described herein. Such embodiments are presented herein for illustrative purposes only.

Additional embodiments will be apparent to persons skilled in the relevant art(s) based on the teachings contained herein.

The present specification and accompanying drawings disclose one or more embodiments that incorporate the features of the disclosed embodiments. The disclosed embodiments merely exemplify the intended scope.

The present disclosure is related to shaping traffic transmitted into a network, such as a network on a chip, in an effort to adaptively reduce congestion on the network. In general, a traffic shaper may throttle the rate at which data from a client (e.g., a CPU core, processing engine, memory controller, cache, peripheral component interconnect express (PCIE) bridge, packet scheduler, etc.) is sent over a network. In general, in some traffic shaping systems, traffic congestion or flow control information may be received from external nodes so that transmission rates may be adapted based on the external conditions. However, in other systems, the congestion or flow control information may be unavailable or impractical to use for traffic shaping purposes. For example, in a mesh-based network with dozens or hundreds of clients accessing the mesh simultaneously, it may be impractical to provide congestion-state feedback for use in traffic control because of the high cost of detecting and distributing this kind of information. Furthermore, the relevance of such information may not be assured by the time it is available for use in traffic flow control. In such cases, it may be desirable to implement the traffic shaper disclosed herein to vary its behavior with a high degree of configurability to self-monitor and throttle.

A traffic shaper may utilize a credit-based system, where the shaper maintains a transaction budget, and as packet transfers occur, the budget is reduced by the cost of a packet transfer (e.g., a packet-transfer cost or a transaction cost). For example, a packet-transfer cost may be proportional to the length of a specific transmission or to the relative weight of a client requesting the transaction compared to its peers. As long as the budget is higher than some threshold (e.g., the cost of one transaction), the client is permitted to transfer a packet. The budget may be replenished by adding transfer credit, and the budget may be capped at some upper limit value.

In the present disclosure, a traffic shaping circuit (i.e., a traffic shaper) with programmable features is described. The traffic shaper allows for automatically and dynamically modifying shaper parameters (e.g., packet-transfer costs and budget limits, among other things), which may effectively throttle the rate of packet transfers into the network. The shaper may comprise a cost table with a plurality of records, where each record may include a respective cost value for transferring a packet into the network, and/or a respective budget limit (e.g., a maximum budget level) for enabling and disabling packet transfers. Each cost table record may be indexed by a dynamic read-pointer that may be increased or decreased to change the current set of parameters utilized by the traffic-shaping circuit. In addition to the cost and budget limit, each table record may store parameters for monitoring a rate of transmission activity and indicating when the read-pointer should increase to the next higher table record (e.g., storing a higher cost or same cost), or for indicating inactivity (e.g., idle cycles) to cause the read-pointer to decrease to the next lower table record (e.g., storing a lower or same cost). In one embodiment, incrementing the read-pointer (e.g., increasing cost) may be governed by exceeding a number (M) of packets transmitted in a number (N) of clock cycles. Decrementing the read-pointer (e.g., lowering the cost) may be governed based on being idle for some number (P) of clock cycles (e.g., clock cycles without a packet transmission). M, N, and P may all be stored within a cost table record. The table records may be ordered. In one example, table records may be ordered based on increasing relative cost. The read-pointer may not wrap at the boundaries of the table, and the initial read-pointer value may be configurable.

Regardless of the cost of a packet transfer, in some embodiments, the traffic-shaping circuit may utilize an epoch timer and epoch credit for adding credit to the budget over time. The epoch timer and epoch credit input may be programmable. In some embodiments, a congestion controller with global, though potentially stale, measurements of congestion in a network may be utilized to modify the epoch time and epoch credit to reduce client transmissions throughout the network fabric (e.g., a mesh fabric).

Use of a cost table and the automatic (e.g., programmable) increases or decreases in pointer values to change the cost of a packet transfer may allow clients that request data transfers some level of burstiness at each packet-transfer cost level before penalizing the client and reducing its transfer rate (e.g., by increasing the cost of each transmission). With a full mesh implementation, the same network links may be shared by numerous clients, so persistent bursts of traffic should likely be discouraged by the network on-ramps. Therefore, the nonlinear behavior of this traffic shaper may be highly productive in reducing traffic congestion.

Embodiments for dynamically shaping packet traffic in a network may be implemented in various ways. For example, <FIG> is a block diagram of a system <NUM> comprising a traffic shaping circuit for dynamically regulating transmissions into a network on a chip, according to an example embodiment. As shown in <FIG>, system <NUM> comprises plurality of traffic shaping circuits <NUM>, a plurality of clients <NUM>, a plurality of transmission resources <NUM>, a plurality of network on-ramps <NUM>, a network on a chip <NUM>, a plurality of nodes <NUM>, and a plurality of network links <NUM>. Each network on-ramp <NUM> comprises a traffic shaping circuit <NUM> and a transmission resource <NUM>, such as a first-in-first-out queue or buffer. System <NUM> is described in detail as follows.

In some embodiments, system <NUM> may comprise a system on a chip (SOC) comprising network on chip <NUM>. Network on a chip <NUM> may be configured to route traffic between components within the SOC. In some embodiments, the SOC may comprise a CPU and may be implemented within an electronic device such as computing and/or communications device (e.g., the SOC may comprise a datacenter processor). Although, the network described with respect to <FIG> is referred to as network on a chip <NUM>, the present disclosure comprising traffic shaping circuit <NUM> may be implemented in any suitable type of network, for example, an IP network, Ethernet network, a wireless network, a network on a chip, etc. Furthermore, system <NUM> may be implemented in an SOC, a desktop or personal computer, a mobile computing device (e.g., a Microsoft® Surface® device, a personal digital assistant (PDA), a laptop computer, a notebook computer, a tablet computer such as an Apple iPad™, a netbook, etc.), a mobile phone (e.g., a cell phone, a smart phone such as an Apple iPhone, a phone implementing the Google® Android™ operating system; a Microsoft® Windows phone, etc.), a wearable computing device (e.g., a head-mounted device including smart glasses such as Google® Glass™, Oculus Rift® by Oculus VR, LLC, etc.), a gaming console/system (e.g., Nintendo Switch®, etc.), an appliance, a set top box, etc..

Network on a chip <NUM> may comprise a plurality of nodes <NUM> communicatively coupled via a plurality of links <NUM>, which provide interconnections for communications among a plurality of clients within the SOC. Each node <NUM> may comprise internal connections configured to couple a set of input links <NUM> to a set of output links <NUM>. Although network on a chip <NUM> is shown in <FIG> as a type of mesh network, the present disclosure is not limited to any specific network topology. For example, traffic shaping circuit <NUM> may be network agnostic and may be implemented in a network having any suitable network topology (e.g., two-dimension, n-dimensional, n-cube, or k-ary n-cube mesh, star, linear, ring, tree, etc.). Network on a chip <NUM> may comprise a constrained or over subscribable interconnect between multiple clients. For example, if every client <NUM> tried to send messages to each other simultaneously, the network may not be able to keep-up with traffic processing which may cause network congestion. In some embodiments, a plurality of clients coupled to network on a chip <NUM> may regulate their own packet transfers with a circuit such as traffic shaping circuit <NUM>. In general, traffic shaping circuit <NUM> is configured to govern traffic in a network where clients may be greedy and could overwhelm the network. For example, a sustained burst of packet transfers of a single client, continuously trying to inject traffic into the network, may oversaturate the network. Traffic shaping circuit <NUM> implemented in conjunction with a client may throttle the client's transmissions into network on a chip <NUM> and reduce excessive bursts of packet transfers.

Each client <NUM> may comprise a device or a node configured to transfer packets via a transmission resource <NUM> and network on a chip <NUM> to a plurality of similar or various types of clients that may also be coupled to network on a chip <NUM>. As shown in <FIG>, there may be a plurality of clients <NUM> that share a transmission resource <NUM>, and are governed by a single traffic shaping circuit <NUM>. In some embodiments, client <NUM> may comprise a processing engine (e.g., a CPU core) or an entity that provides data for transmission such as a memory controller or a cache (e.g., an L2 cache, L3 cache, L4 cache), a PCIE Bridge, etc. For example, client <NUM> may provide a command for, or may request, data to be transmitted over network on a chip <NUM> to another client, or may provide the data itself for transmission via transmission resource <NUM>. Transmission resource <NUM> may be communicatively coupled to client <NUM> and traffic shaping circuit <NUM>, and may comprise any suitable logic, circuitry, interfaces and/or code that is configurable to connect client <NUM> to network on a chip <NUM>, for example, via network on-ramp <NUM>, and control the transmission of packets for client <NUM> to another client coupled to network on a chip <NUM>. In some examples, transmission resource <NUM> may comprise a first-in-first-out queue or buffer to store messages until the network accepts them. Transmission resource <NUM> may also comprise circuits to select a routing path or otherwise adapt or classify messages for transport on the network on a chip <NUM>.

Network on-ramp <NUM> may comprise a communications link from transmission resource <NUM> to one or more nodes <NUM> and/or one or more links <NUM> in network on a chip <NUM>. A packet transfer may comprise the transmission of data (e.g., a transmission unit or message) from client <NUM> to another client coupled to network on a chip <NUM>. The packet transfer may be referred to as a transfer, a transaction, or a transmission. In some embodiments, each client <NUM> coupled to network on a chip <NUM> may have its own network on-ramp <NUM> and shaping circuitry <NUM>. Alternatively, network on-ramp <NUM> and shaping circuit <NUM> may be coupled to and support communications for multiple clients <NUM> where the transfer cost function may be adjusted for each client or client type.

Traffic shaping circuit <NUM> may be configured to control the timing, or rate, of packet transfers into network on a chip <NUM> by adjusting the cost of transferring a packet relative to a budget (and other traffic control parameters), based on feedback from transmission side measurements rather than feedback from the network or receiver side (e.g., congestion notifications, round trip delay, etc.). In general, traffic shaping circuits <NUM> may be disposed at, or be a part of, the on-ramps of a network between a client and a router, and may throttle network access by greedy clients that may otherwise consume too much of the network's resources. In other words, traffic shaping circuit <NUM> may be configured to make a decisions as to when and/or at what rate packets may be transmitted on behalf of client <NUM> to control the amount of traffic on network on a chip <NUM>.

Traffic shaping circuit <NUM> may operate in various ways to perform its functions. For instance, <FIG> is a flowchart <NUM> of a method for controlling a packet transfer rate by dynamically adjusting packet-transfer cost and/or budget parameters, according to an example embodiment. In an embodiment, traffic shaping circuit <NUM> may operate according to flowchart <NUM>. Flowchart <NUM> is described as follows with reference to <FIG>, <FIG>, and <FIG>.

<FIG> is a block diagram of a system <NUM> illustrating functions performed by a traffic shaping circuit that dynamically adjusts transfer cost and/or budget parameters, according to an example embodiment. For example, system <NUM> comprises traffic shaping circuit <NUM>, client <NUM>, transmission resource <NUM>, network on-ramp <NUM>, transfer enable logic <NUM>, traffic-monitoring logic <NUM>, a cost-adjustment controller <NUM>, and traffic gating logic <NUM>. System <NUM> further comprises a transfer enable <NUM>, a transfer notification <NUM>, a cost-adjustment signal <NUM>, a packet-transfer cost <NUM>, a cost table <NUM>, packet-transfer credits <NUM>, budget credit cycles <NUM>, a budget limit <NUM>, a transfer-rate threshold <NUM>, and an idle-time threshold <NUM>.

<FIG> is a block diagram of a system <NUM> comprising a traffic shaping circuit that dynamically adjusts packet-transfer cost and/or budget limit parameters, according to an example embodiment. System <NUM> comprises, among other things, traffic shaping circuit <NUM>, client <NUM>, transmission resource <NUM>, transfer enable logic <NUM>, traffic-monitoring logic <NUM>, cost-adjustment controller <NUM>, and traffic gating logic <NUM>. System <NUM> further comprises transfer enable <NUM>, transfer notification <NUM>, cost-adjustment signals 326A and 326B, packet-transfer cost <NUM>, cost table <NUM>, packet-transfer credit <NUM>, budget credit cycles <NUM>, budget limit <NUM>, transfer-count threshold <NUM>, transfer-cycles count threshold <NUM>, and idle-time threshold <NUM>. Also shown in system <NUM> are a multiplexer <NUM>, a multiplexer <NUM>, a budget register <NUM>, an idle-cycle counter <NUM>, a packet-transfer counter <NUM>, and a transfer-cycle counter <NUM>.

In some embodiments systems <NUM> and <NUM> may be implemented within system <NUM>. For purposes of illustration, systems <NUM> and <NUM> are described in detail as follows with respect to flowchart <NUM> of <FIG>.

Flowchart <NUM> begins with step <NUM>. In step <NUM>, a packet-transfer cost and/or a budget limit is determined for transferring packets into a network on a chip by a transmission resource on behalf of a client. Transfer-enable logic <NUM> may be configured to store and determine budget value <NUM>. Budget value <NUM> may be utilized to determine whether packet transfers are enabled. For example, if budget value <NUM> drops too low, packet transfers may be disabled. For each packet that is transferred onto network on a chip <NUM>, a value of packet-transfer cost <NUM> may be deducted from budget value <NUM> (e.g., packet-transfer cost <NUM> may be stored as a negative value). Moreover, one or more packet-transfer credits <NUM> may be added to budget value <NUM> at budget-credit cycles <NUM>, which may be received by transfer-enable logic <NUM> as a timing signal (e.g., a programmable epoch timer may output budget-credit cycles <NUM>). In some instances both of the credit and the cost may be applied to budget value <NUM> concurrently (e.g., a value of packet-transfer credit <NUM> less packet-transfer cost <NUM> may be added to budget value <NUM>). In some embodiments, budget value <NUM> may be capped at budget limit <NUM> such that if an amount of packet transfer credit <NUM> being added to budget value <NUM> causes budget value <NUM> to be greater than budget limit <NUM>, budget limit <NUM> may be stored as budget value <NUM> instead of adding the packet-transfer credit <NUM> value to the budget. A plurality of packet transfer cost <NUM> values and/or a plurality of budget limit <NUM> values may be stored in cost table <NUM>, and current values utilized in transfer-enable logic <NUM> for packet transfer cost <NUM> and/or budget limit <NUM> may be determined by reading a record from cost table <NUM>.

In step <NUM>, a rate of packet transfers by the transmission resource is monitored. For example, transmission resource <NUM> may be configured to transmit packets onto network on-ramp <NUM> and network on a chip <NUM> on behalf of client <NUM>. Traffic gating logic <NUM> may be configured to facilitate a handshake between client <NUM> and transmission resource <NUM> for each packet transmission, and may provide transfer notification <NUM> to transfer-monitoring logic <NUM> each time a packet-transfer is confirmed. Traffic-monitoring logic <NUM> may be configured to determine a rate of packet transfers and/or an idle period of transmission resource <NUM> based on transfer notification <NUM> signals.

In step <NUM>, the packet-transfer cost and/or the budget limit are modified for subsequent packet transfers performed by transmission resource <NUM> based on the monitored rate of packet transfers. For example, traffic-monitoring logic <NUM> may be configured to analyze the rate of packet transfers based on transfer notification signals <NUM>, and depending on the rate, traffic monitoring logic <NUM> may transmit cost-adjustment signal <NUM> (or cost-adjustment signal 326A of <FIG>) to cost-adjustment controller <NUM>. In this regard, traffic monitoring logic <NUM> may transmit cost adjustment signal <NUM> (or 326A) if the measured packet transfer rate exceeds transfer-rate threshold <NUM> (described in more detail with respect to <FIG>, <FIG>, and <FIG>). Cost-adjustment controller <NUM> may be configured to modify the value of packet-transfer cost <NUM> and/or the value of budget limit <NUM> based on cost adjustment signal <NUM> (described in more detail with respect to <FIG> and <FIG>). The modified packet-transfer cost <NUM> value and/or budget limit <NUM> value may be applied when adjusting budget value <NUM> for one or more subsequent packet transfers by transmission resource <NUM>. In this manner, the rate of transferring packets may be decreased if packet-transfer cost <NUM> is increased such that budget <NUM> drains more quickly as larger costs are applied per packet transfer. Alternatively, or in addition, the rate of transferring packets may be decreased if budget limit <NUM> is reduced, as this may also cause budget <NUM> to drain sooner by capping budget value at a lower level then than used for previous transfers. In other words, the packet transfer rate may be reduced (or throttled) as packet transfers are momentarily disabled, more often over time, due to raising packet-transfer cost <NUM> and/or lowering budget limit <NUM>. As such, a sustained burst of packet transfers for client <NUM> may be regulated to avoid oversaturation of network on a chip <NUM>, where traffic shaping circuit <NUM> self-adjusts in reaction to bursts of packet transfers occurring in transmission resource <NUM> (e.g., without awareness of how the rest of network on a chip <NUM> is handling traffic).

Cost-adjustment controller <NUM> may operate in various ways to perform its functions. For instance, <FIG> is a block diagram of a system <NUM> comprising a cost- adjustment controller with a cost table for storing parameters for shaping packet transmission rates, according to an example embodiment. Moreover, <FIG> is a block diagram of a system <NUM> comprising the cost table of <FIG> and the stored parameters utilized for shaping packet transmission rates, according to an example embodiment.

In some embodiments systems <NUM> and <NUM> may be implemented within systems <NUM>, <NUM>, and/or <NUM>. For purposes of illustration, systems <NUM> and <NUM> are described in detail as follows. In some embodiments, system <NUM> may comprise cost-adjustment controller <NUM>, transfer enable logic <NUM>, and traffic monitoring logic <NUM>. Cost-adjustment controller <NUM> may comprise cost table <NUM> and cost-table-read-pointer generator <NUM>. Cost table <NUM> may comprise a plurality of records comprising record <NUM>, record <NUM>, record <NUM>, record <NUM>, record <NUM>, and record <NUM>, which may be referred to as records <NUM>-<NUM>.

In some embodiments, system <NUM> may comprise cost table <NUM> and records <NUM>-<NUM>. Records <NUM>-<NUM> may each comprise a respective set of parameters where each respective set of parameters may comprise one or more of a packet-transfer cost <NUM>, a budget limit <NUM>, a transfer-rate threshold <NUM>, and an idle-time threshold <NUM>. Transfer-rate threshold <NUM> may be represented in various ways. For example, in some embodiments, transfer-rate threshold <NUM> may comprise separate parameters for a count and a time duration, where each separate parameter may be stored in cost table <NUM> as a transfer-count threshold <NUM> and a transfer-cycle count threshold <NUM>.

Although six indexed records <NUM>-<NUM> are shown in cost table <NUM> and five parameters <NUM>, <NUM>, <NUM>, <NUM>, and <NUM> are shown in each indexed record, in some embodiments, cost table <NUM> may comprise fewer or more records of parameters, and each record of cost table <NUM> may comprise fewer or more parameters.

In some embodiments, records <NUM>-<NUM> may be stored and/or indexed in cost table <NUM> in a specified order. For example, records <NUM>-<NUM> may be ordered based on values of their respective packet-transfer costs. Cost-table-read-pointer generator <NUM> may be configured to selectively output from cost table <NUM>, a higher packet-transfer cost or a lower packet-transfer cost based on an indication of cost-adjustment signal <NUM> (e.g., 326A for a higher cost and 326B for a lower cost) and the order of records <NUM>-<NUM> for modifying the packet-transfer cost. In some embodiments, the lowest record index (e.g., record <NUM>) may store the lowest transfer cost <NUM> value, and as the indices (or pointer addresses) increase (e.g., from record <NUM> to <NUM>), each successive record may store an increasing transfer cost <NUM> value. In this manner, the packet-transfer cost <NUM> may be increased or decreased by incrementing or decrementing the pointer address generated by cost-table-read-pointer generator <NUM>. Cost-adjustment signal <NUM> may indicate whether to increment or decrement the pointer address. Referring to <FIG>, in some embodiments, cost-adjustment signal <NUM> may comprise two separate signals 326A and 326B, where 326A indicates that the pointer address should be incremented (e.g., to point to a higher packet-transfer cost value) and 326B indicates that the pointer address should be decremented (e.g., to point to a lower packet-transfer cost value). However, the disclosure is not limited to any specific way of ordering records in cost table <NUM>, or any specific manner of selecting a particular packet-transfer cost <NUM> with a read pointer from cost-table-read-pointer generator <NUM>.

In some embodiments, records in cost table <NUM> may be ordered or sorted based on budget limit <NUM> values, such that cost-adjustment signal <NUM> may directly indicate whether budget limit <NUM> should be increased or decreased to shape packet transfer rates of client <NUM> for subsequent packet transfers into network on a chip <NUM>.

Cost-adjustment controller <NUM> may be configured to output parameter values from a record of cost table <NUM> that is pointed to by cost-table-read-pointer generator <NUM> for use in enabling packet transfers and generating cost adjustment signal <NUM> (e.g., 326A and 326B). For example, cost-adjustment controller <NUM> may read a selected record and transmit a corresponding packet-transfer cost <NUM> value and/or budget limit <NUM> value to transfer-enable logic <NUM>. A corresponding transfer-rate threshold <NUM> value (or transfer-count threshold <NUM> and transfer-cycle count threshold <NUM> values) and idle-time threshold <NUM> value (described in more detail below) of the same record may be transmitted to traffic monitoring logic <NUM> for monitoring the packet-transmission rate and a length of time that transmission resource <NUM> may be idle.

In some embodiments, values of an parameters stored in cost table <NUM> may be configurable (e.g., packet-transfer cost <NUM>, budget limit <NUM>, transfer rate threshold <NUM> (or transfer-count threshold <NUM> and transfer-cycle count threshold <NUM>), and idle-time threshold). Referring to the example in <FIG>, values for packet-transfer cost <NUM>, budget limit <NUM> idle-time threshold <NUM>, transfer-count threshold <NUM>, transfer-cycle count threshold <NUM> values, and idle-time threshold <NUM> may be configured in cost table <NUM>, at a record pointed to by cost-table-read-pointer generator <NUM>, when parameter values and a set-value signal are received based on cost-table configuration and status registers (CSRs).

Traffic shaping circuit <NUM> may operate in various ways to perform its functions. For instance, <FIG> is a flowchart <NUM> of a method for dynamically regulating transmissions into a network on a chip, according to an example embodiment. Flowchart <NUM> may be performed as part of flowchart <NUM> (<FIG>), such as beginning at step <NUM>. In an embodiment, traffic shaping circuit <NUM> may operate according to flowchart <NUM>. Flowchart <NUM> is described as follows with reference to <FIG>, <FIG>, <FIG>, <FIG>, and <FIG>.

Flowchart <NUM> includes step <NUM>. In step <NUM>, packet transfers into the network on the chip by the transmission resource may be selectively enabled or disabled based on a budget value. As described above, budget value <NUM> may be utilized to determine whether packet transfers are enabled such that if budget value <NUM> drops too low, packet transfers may be disabled (thus, stopping or slowing network traffic). Budget value <NUM> may be decreased by the current transfer cost <NUM> value for each packet that is transferred onto network on a chip <NUM>, and may be increased with packet-transfer credits <NUM> at each budget-credit cycle <NUM>. If both conditions occur concurrently, both of the credit and the cost may be applied to budget value <NUM>. Moreover, budget value <NUM> may be capped at budget limit <NUM>, which may be configurable per packet-transfer cost level. Capping budget value <NUM> at budget limit <NUM> may provide for configuring a level of burst tolerance that is permitted for client <NUM>. This may be useful when budget value <NUM> may not be used for a number of cycles and then suddenly incurring a highly demanding job. By providing a configurable budget limit <NUM>, transmission bursts may be capped using a fewer number of shaping resources provided in traffic shaping circuit <NUM>.

In one embodiment, budget value <NUM> may be accumulated and stored in budget register <NUM>, which may comprise one or more D flip-flops (e.g., see <FIG>). Although only one budget register <NUM> is shown in the example of <FIG>, there may be a plurality of budget register <NUM> that store budget value <NUM>. The most significant bit (MSB) output from budget register <NUM> may indicate whether transfers are enabled (e.g., a zero MSB may indicate that transfers are not enabled, and an MSB of one may indicate that transfers are enabled). In this example, if there are seven D flip-flops storing budget values <NUM>, the MSB may indicate that packet transfers are enabled for budget values of <NUM> - <NUM>, and disabled for budget values of <NUM> and lower. However, as described above, the value stored as budget value <NUM> may be limited on the high-end by budget limit <NUM> such that, in this example, packet transfers may be enabled where budget values <NUM> range from <NUM> to the current value of budget limit <NUM>. Notwithstanding, the disclosure is not limited to any specific range of budget values <NUM>, or any specific type of storage device for budget value <NUM>.

As described above, cost table <NUM> may store a plurality of packet-transfer cost <NUM> values and/or a plurality of budget limit <NUM> values, where the current values utilized in transfer-enable logic <NUM> for packet-transfer cost <NUM> and/or budget limit <NUM> may be determined by reading a record from cost table <NUM> based on cost-adjustment signal <NUM>. Budget value <NUM> may be updated as a result of various events. Referring to the example shown in <FIG>, in response to receiving a timing signal of budget-credit cycles <NUM>, multiplexer <NUM> may be configured to select packet-transfer credit <NUM> as an output from the multiplexer. In some embodiments, the time interval for budget credit cycles <NUM> and/or the credit value for packet-transfer credit <NUM> may be programmable (e.g., via configuration and status registers (CSR)). In response to receiving a packet-transfer notification <NUM> signal, multiplexer <NUM> may be configured to select a current transfer-cost <NUM> value, which may be pointed to by a read pointer of cost-table-read-pointer generator <NUM>, as the multiplexer output. In response to receiving, concurrent, budget-credit cycles <NUM> output and packet-transfer notification <NUM>, multiplexer <NUM> may be configured to select a value of packet-transfer credit <NUM> less the current transfer-cost <NUM> value as the multiplexer output. Moreover, in the absence of both of the budget credit cycles <NUM> output and the packet-transfer notification <NUM>, multiplexer <NUM> may be configured to select zero as the multiplexer output. The output of multiplexer <NUM> may be added to the current budget value <NUM>, and if the sum of multiplexer <NUM> output and current budget value <NUM> is greater than budget limit <NUM>, multiplexer <NUM> may be configured to select budget limit <NUM> as a multiplexer output, which may be entered as a new budget value <NUM> into budget register <NUM> (e.g., the D flip-flops). If the sum of multiplexer <NUM> output and current budget value <NUM> is not greater than budget limit <NUM>, multiplexer <NUM> may be configured to select the sum of multiplexer <NUM> output and current budget value <NUM> as the multiplexer <NUM> output, which may be entered as the new budget value <NUM> in budget register <NUM> (e.g., the D flip-flops).

In the example shown in <FIG>, the value of transfer enable <NUM> may also depend upon whether traffic-shaping circuit <NUM> is enabled to perform its functions. For example, if a shaper-enable input signal is low, indicating that traffic-shaping circuit <NUM> is disabled, transfer enable <NUM> will remain high such that packet transfers by client <NUM> and transmission resource <NUM> remain enabled without regulation by traffic shaping circuit <NUM>. On the other hand, if the shaper-enable input signal is high, indicating that traffic-shaping circuit <NUM> is enabled to function, then transfer enable <NUM> output may depend on the MSB of budget value <NUM>.

In step <NUM>, in response to transferring a packet into the network on the chip by the transmission resource, the budget value may be modified based on a packet-transfer cost. For example, as described above, traffic-gating logic <NUM> may be configured to facilitate a handshake between client <NUM> and transmission resource <NUM> for transferring packets into network on a chip <NUM>. In the example shown in <FIG>, client <NUM> may indicate when valid data is available to be transferred, and in response, traffic-gating logic <NUM> may communicate a data ready condition to transmission resource <NUM> under the condition that transfer enable <NUM> indicates that packet transfers are enabled. Moreover, transmission resource <NUM> may indicate when it is ready (e.g., resource ready) to transfer a packet onto network on-ramp <NUM> of network on a chip <NUM>. Traffic-gating logic <NUM> may be configured to output a packet-transfer notification <NUM> under the condition that both of the data ready condition and resource ready conditions are high. Packet-transfer notification <NUM> may indicate that a packet comprising the valid data has been transmitted onto network on-ramp <NUM> and/or into network on a chip <NUM>. Packet-transfer notification <NUM> may be sent to transfer-enable logic <NUM> and may cause budget value <NUM> to be reduced by the currently selected packet-transfer cost <NUM> from cost table <NUM>, which may be pointed to by a read pointer of cost-table-read-pointer generator <NUM>, as described above.

In step <NUM>, a rate of packet transfers into the network on the chip, which are performed by the transmission resource, may be monitored. For example, as described above, traffic-monitoring logic <NUM> may be configured to determine a rate of packet transfers and/or an idle period of transmission resource <NUM> based on transfer notification <NUM> signals. In the example shown in <FIG>, transfer monitoring logic <NUM> may comprise a packet-transfer counter <NUM> and a transfer-cycles counter <NUM>, and may receive a transfer-rate threshold <NUM> from a record of cost table <NUM> based on a current read pointer value of cost-table-read-pointer generator <NUM>. In some embodiments, transfer-rate threshold may comprise transfer-count threshold <NUM> and transfer-cycles threshold <NUM>. Packet-transfer counter <NUM> may be configured to increment each time a packet-transfer notification <NUM> signal is received from traffic-gating logic <NUM>. Transfer-cycles counter <NUM> may be configured to count transfer clock cycles until it reaches transfer-cycles threshold <NUM> or until the counter is cleared in response to a packet-transfer notification <NUM>. Transfer-cycles counter <NUM> may begin counting again after it is cleared.

Transfer monitoring logic <NUM> may comprise an idle-cycle counter <NUM> and receive transfer-cycles threshold <NUM> from a record of cost table <NUM> based on a current read pointer value of cost-table-read-pointer generator <NUM>. Idle-cycles counter <NUM> may be configured increment at each transfer clock cycle while transmission resource <NUM> stands idle or is waiting to transfer the next packet onto network on-ramp <NUM>. Idle-cycles counter <NUM> may clear (or reset) when a packet is transferred onto network on-ramp <NUM> (e.g., based on receiving a packet-transfer notification <NUM>).

In step <NUM>, a cost-adjustment signal may be generated based on the rate of packet transfers into the network on the chip by the transmission resource. In the example of <FIG>, traffic monitoring logic <NUM> may be configured to compare a current packet-transfer count from packet-transfer counter <NUM> to the current transfer-count threshold <NUM> from cost table <NUM>, and if the transfer-count <NUM> becomes equal to the transfer-count threshold <NUM> before the count of transfer-cycles counter <NUM> matches transfer-cycles threshold <NUM>, traffic-monitoring logic <NUM> may be configured to transmit a cost-adjustment signal <NUM> or 326A to table-read-pointer generator <NUM> (e.g., to increment the read pointer of cost-table-read-pointer generator <NUM>). Moreover, traffic monitoring logic <NUM> may be configured to compare a count value of transfer-cycle counter <NUM> to the current transfer-cycle threshold <NUM> from cost table <NUM>, and if the count of transfer-cycle counter <NUM> becomes equal to the transfer-cycle threshold <NUM> before the packet-transfer count from packet-transfer counter <NUM> becomes equal to transfer-count threshold <NUM>, traffic-monitoring logic <NUM> may be configured to clear (e.g., reset) packet-transfer counter <NUM> and transfer-cycle counter <NUM>, and begin again to count packet transfers (e.g., packet-transfer notifications <NUM>) and transfer clock cycles without generating a cost-adjustment signal <NUM> (e.g., maintaining the same read-pointer output from cost-table-read-pointer generator <NUM>).

Furthermore, traffic monitoring logic <NUM> may be configured to compare a current count of idle-cycles counter <NUM> to the current idle-time threshold <NUM> from cost table <NUM>, and if the current idle-cycles count <NUM> becomes equal to the idle-time threshold <NUM>, traffic-monitoring logic <NUM> may be configured to transmit a cost-adjustment signal <NUM> or cost-adjustment signal 326B to cost-table-read-pointer generator <NUM> (e.g., for decrementing the read pointer of cost-table-read-pointer generator <NUM>). In some embodiments, other cost-decreasing mechanisms may be implemented. For example, traffic monitoring logic <NUM> may be configured to compare packet-transfer rates to a low transfer-rate threshold to determine when to transmit a cost-adjustment signal <NUM> for decrementing read pointer of cost-table-read-pointer generator to lower a packet-transfer cost <NUM>.

In step <NUM>, the packet-transfer cost may be modified in response to the cost-adjustment signal for a subsequent-packet transfer into the network on the chip by the transmission resource. For example, the current packet-transfer cost <NUM> may be modified by reading a higher or lower packet-transfer cost <NUM> from cost table <NUM> for use in transfer-enable logic <NUM>. As described above, in the example of <FIG>, in response to a count value of transfer-counter <NUM> becoming equal to the transfer-count threshold <NUM> before the count of transfer-cycles counter <NUM> matches transfer-cycles threshold <NUM>, traffic-monitoring logic <NUM> may transmit a cost-adjustment signal <NUM> or 326A to table-read-pointer generator <NUM>. As a result, this cost-adjustment signal <NUM> or 326A may indicate that the read pointer of cost-table-read-pointer generator <NUM> should be incremented, which may result in reading a higher packet-transfer cost <NUM> value from cost table <NUM>. In another example, as described above, in response to a current count of idle-cycles counter <NUM> becoming equal to idle-time threshold <NUM>, traffic-monitoring logic <NUM> may transmit a cost-adjustment signal <NUM> or cost-adjustment signal 326B to cost-table-read-pointer generator <NUM>. As a result, this cost-adjustment signal <NUM> or 326B may indicate that the read pointer of cost-table-read-pointer generator <NUM> should be decremented, which may result in reading a lower packet-transfer cost <NUM> value from cost table <NUM>. Transfer-enable logic <NUM> may be configured to utilize the higher or lower packet-transfer cost <NUM> value (e.g., an adjusted cost value) in applying a cost reduction to budget value <NUM> in response to receiving a subsequent packet-transfer notification <NUM>. For example, in response to transferring the subsequent packet into network on the chip <NUM> by transmission resource <NUM>, transfer-enable logic <NUM> may be configured to modify budget value <NUM> based on the adjusted packet-transfer cost <NUM> for selectively enabling or disabling a further-subsequent-packet transfer into network on the chip <NUM> by transmission resource <NUM>. The behavior of the shaper resulting from variations in the read pointer and different cost table entries may be nonlinear in time, and depends upon the sequence of transmissions generated by the client.

As described above, in some embodiments, cost table <NUM> entries may be configured such that the lowest address in that table comprises the lowest packet-transfer cost <NUM> value and any higher address has a non-decreasing cost value (e.g., each increasing record index stores the same or a higher cost value than the prior record). In this configuration, bursts of packet traffic may result in increased table read pointer values and higher selected packet-transfer cost <NUM> values, while increasing transmitter idle periods may result in lower table read pointer values and lower selected packet-transfer cost <NUM> values from cost table <NUM>. Various models may be utilized to generate packet-transfer cost change patterns (e.g., for increasing or decreasing packet-transfer costs). For example, an exponential cost change pattern or a linear type of cost change pattern may be utilized. In an example of an exponential pattern, the relative packet-transfer cost in successive cost table <NUM> records may double the previous record's cost. In an example of a linear pattern, each packet-transfer cost <NUM> value in cost table <NUM> may be proportional to its record index plus a constant value. Budget limits <NUM> and/or the high-end of the range in budget value <NUM> may also be modified to control traffic bursts and modify burst tolerance. In this regard, traffic shaping circuit may be highly configurable to self-adjust in reaction to its own traffic bursts without global awareness of traffic on network on the chip <NUM>. The behavior of traffic shaping may be linear or non-linear depending upon how cost table <NUM> parameters are configured.

Example linear and exponential cost adjustment scenarios are provided below and are presented using Python language. Table read pointers may be incremented based on the variable "i" from zero to some number of records in cost table <NUM>. The term "M" may represent a number (M) of packets transmitted in a number "N" of epoch clock cycles for incrementing the table read pointer. The term "P" may represent some number of idle clock cycles (e.g., clock cycles without a packet transmission) for decrementing the table read pointer. M, N, and P may all be stored within a cost table record. <IMG>
<IMG>.

Embodiments described herein may be implemented in hardware, or hardware combined with software and/or firmware. For example, embodiments described herein may be implemented as computer program code/instructions configured to be executed in one or more processors and stored in a computer readable storage medium. Alternatively, embodiments described herein may be implemented as hardware logic/electrical circuitry.

As noted herein, the embodiments described, including but not limited to, systems <NUM>, <NUM>, <NUM>, <NUM>, and <NUM> along with any components and/or subcomponents thereof, as well any operations and portions of flowcharts/flow diagrams described herein and/or further examples described herein, may be implemented in hardware, or hardware with any combination of software and/or firmware, including being implemented as computer program code configured to be executed in one or more processors and stored in a computer readable storage medium, or being implemented as hardware logic/electrical circuitry, such as being implemented together in a system-on-chip (SoC), a field programmable gate array (FPGA), an application specific integrated circuit (ASIC), a trusted platform module (TPM), and/or the like. A SoC may include an integrated circuit chip that includes one or more of a processor (e.g., a microcontroller, microprocessor, digital signal processor (DSP), etc.), memory, one or more communication interfaces, and/or further circuits and/or embedded firmware to perform its functions.

Embodiments described herein may be implemented in one or more computing devices similar to a mobile system and/or a computing device in stationary or mobile computer embodiments, including one or more features of mobile systems and/or computing devices described herein, as well as alternative features. The descriptions of computing devices provided herein are provided for purposes of illustration, and are not intended to be limiting. Embodiments may be implemented in further types of computer systems, as would be known to persons skilled in the relevant art(s).

Referring again to <FIG>, traffic-shaping circuit <NUM> may be implemented in a SOC comprising network on a chip <NUM>. Budget register <NUM> may store budget value <NUM> that may be accumulated over time based on budget-credit cycles <NUM> output from a programmable epoch timer. Each time the epoch timer expires, a programmable amount of packet-transfer credit <NUM> may be added to budget <NUM>. For each packet transfer that is sent out into network on a chip <NUM>, the value of a current transfer cost <NUM> may be incurred and subtracted from budget value <NUM>. Once budget value <NUM> falls below its low threshold, traffic shaping circuit <NUM> may disable further traffic at network on-ramp <NUM> until the next epoch timer expiry. Budget register <NUM> may store budget value <NUM>, which may comprise a user-defined bit width. The MSB of budget value <NUM>, output from budget register <NUM>, may indicate whether a packet transfer is enabled (e.g., may indicate the low threshold for budget value <NUM> at half-scale of the numerical range of budget value <NUM>). Utilizing the MSB to act as the low threshold for budget value <NUM> may simplify critical-path timing for the data-valid and data-ready handshake in traffic-gating logic <NUM>, as well as for feedback towards other sections (e.g., traffic-monitoring logic <NUM> and transfer-enable logic <NUM>) of traffic shaping circuit <NUM> in comparison to threshold comparison circuits involving more bits.

Utilizing an adjustable packet-transfer cost <NUM> value provides for better tuning of packet-transfer rates at network on-ramp <NUM>. To implement an adjustable packet-transfer cost <NUM>, cost table <NUM>, which may comprise a user-definable size, is provided to allow for many different configurations. Each record <NUM>-<NUM> in cost table <NUM> may hold several parameters that define operations of traffic shaping circuit <NUM>. In one example, the records may be arranged from lowest packet-transfer cost (record <NUM>) to higher cost (record N), and the current cost index (e.g., the current record selection of cost-table-read-pointer generator <NUM>) may be controlled based on monitored packet traffic behavior (e.g., packet-transfer notifications <NUM>) and cost table <NUM> configuration. The cost table index selection may be incremented as traffic-shaping circuit <NUM> allows more transfers, which in turn, may depress the rate of packet transfers. Moreover, as idle-cycles accumulate over time without packet transfers, the cost table index selection may be decreased in order to ease restrictions on subsequent packet transfers. Each record of cost table <NUM> may include fields comprising the following parameters (e.g., where cost values may be generally non-decreasing for increasing cost index). Packet-transfer cost <NUM> may specify the cost that is subtracted from budget value <NUM> for each packet transaction that is permitted. Budget limit <NUM> may specify a limit value (e.g., a maximum budget value) indicating the point at which budget register <NUM> saturates. This limit value may determine how long traffic-shaping circuit <NUM> can sustain a traffic burst at the current cost index before packet transfers are disabled. Transfer-count threshold <NUM> and transfer-cycle-count threshold <NUM> (or transfer-rate threshold <NUM>) may specify how many packet transfers at the currently selected packet-transfer cost, over how many packet transfer time cycles, may trigger a move to select a higher packet-transfer cost <NUM> entry in cost table <NUM>. Idle-time threshold <NUM> may specify how much time (e.g., in packet transfer clock cycles) must pass since the most recent packet transaction before the pointer of cost-table-read-pointer generator <NUM> is decremented, to point to a lower value cost entry in cost table <NUM>.

Claim 1:
A traffic shaping circuit (<NUM>) communicatively coupled between a client (<NUM>) and a transmission resource (<NUM>) that is operable to regulate packet transfers into a network (<NUM>) on behalf of the client (<NUM>), the traffic shaping circuit (<NUM>) comprising:
transfer-enable logic (<NUM>) configured to:
selectively enable or disable (<NUM>) packet transfers into the network (<NUM>) by the transmission resource (<NUM>) based on a budget value (<NUM>); and
in response to transferring a packet into the network (<NUM>) by the transmission resource (<NUM>), modify (<NUM>) the budget value (<NUM>) based on a packet-transfer cost (<NUM>);
traffic-monitoring logic (<NUM>) configured to:
monitor (<NUM>) a rate of packet transfers into the network (<NUM>) performed by the transmission resource (<NUM>); and
generate (<NUM>) a cost-adjustment signal (<NUM>) based on the rate of packet transfers into the network (<NUM>) by the transmission resource (<NUM>); and
a cost-adjustment controller (<NUM>) configured to:
modify (<NUM>) the packet-transfer cost (<NUM>) in response to the cost-adjustment signal (<NUM>) for a subsequent-packet transfer into the network (<NUM> by the transmission resource (<NUM>);
wherein the budget value (<NUM>) is capped at a budget limit (<NUM>) that is configurable per packet-transfer cost level, wherein the capped budget value is configuring a level of burst tolerance that is permitted for the client.