Patent Description:
In network devices that provide queueing, there is a trade-off on the amount of buffering required at various queuing points. Multiple network strategies are utilized to minimize the amount of queuing to reduce jitter and latency for data traffic in order to enhance a user's Quality of Experience. But there are multiple scenarios, such as transmission over a shared resource such as air (e.g., WiFi, <NUM>, LTE, <NUM>, and the like) or fiber (e.g., passive optical networks (PON) such as gigabit passive optical network [GPON], <NUM> gigabit, symmetrical PON [XGS-PON], next-generation PON [NG-PON], ethernet PON [EPON], and the like), where queueing memory requirements can be very high and difficult to predict.

Equipment vendors always strive to minimize power and cost while increasing performance. While memory external to a packet processor (e.g., DDR memory) is inexpensive and scalable, external memory has a high-power utilization cost and lower performance when such memory is accessed relative to processor internal memory. On the other hand, such internal memory is expensive and not very scalable for the cost but has low power utilization and higher performance. <CIT> discloses a method for management of traffic buffering in a passive optical network. The memory management method includes receiving a plurality of data packets from a stream of packets. A plurality of packet descriptors associated with each data packet is stored in a configurable first queue. The first queue includes a plurality of cache slots and is managed in an internal memory. A state of the first queue is identified. In response to the state of the first queue meeting a predetermined threshold, packet descriptors from a tail cache slot of the first queue are transferred to a second queue. The second queue is managed in an external memory. <CIT> discloses memory management unit, including an external memory interface for communicating data from at least one of a first and second data port interface and an external memory. A communication channel is provided, with the communication channel communicating data and messaging information between the at least one first data port interface, the at least one second data port interface, the internal memory, and the memory management unit. The memory management unit directs data from one of the first data port and the second data port to one of the internal memory and the external memory interface, according to a predetermined algorithm.

According to the invention there is provided a method for storing and accessing queued packet data in a network device, a network node configured to route network packets from an ingress network to one or more egress networks, and a non-transitory, computer-readable storage medium embodiment computer program code, as defined by the appended claims.

Embodiments of the present invention may be better understood by referencing the accompanying drawings.

The use of the same reference symbols in different drawings indicates identical items unless otherwise noted.

The present invention provides a mechanism to maximize utilization of internal memory for packet queuing in network devices, while providing an effective use of both internal and external memory to achieve high performance, high buffering scalability, and minimizing power utilization. Embodiments initially store packet data received by the network device in queues supported by an internal memory. If internal memory utilization crosses a predetermined threshold, a background task performs memory reclamation by determining those queued packets that should be targeted for transfer to an external memory. Those selected queued packets are transferred to external memory and the internal memory is freed. Once the internal memory consumption drops below a threshold, the reclamation task stops. Embodiments provide low power consumption because while the internal memory consumption is below the threshold, the power consumption is lowest possible (e.g., just internal memory utilization). When the internal memory is fully utilized for buffering, and external memory is utilized for some queue storage, the power consumption is lower than a standard solution that stores all queued packet data in an external memory.

Typical network devices, such as routers, switches, and optical network units (ONUs) receive network data packets at a network interface, process those packets to determine a destination or otherwise modify the packet, and then transmit the packet from an egress network interface. Upon receiving the data packets, the network device stores the contents of the data packets in a job queue and then, upon processing, can store the contents of the processed data packet in a queue associated with an egress port related to the egress network interface while waiting for availability of the egress network. For speed and low power consumption, memory that is internal to the processor of the network device can be used to store the data packet queues. But such memory is limited and is not generally scalable. Memory external to the processor, such as DDR memory, can be used to provide scalability, but such external memory carries both a speed and power consumption penalty, and thus is not as desirable to use. Embodiments of the present invention provide a mechanism that uses both the internal memory and the external memory for packet queuing, thereby providing both speed, low power consumption, and scalability.

<FIG> is a simplified block diagram illustrating an example network environment <NUM> having network devices that can incorporate embodiments of the present invention. The illustrated network environment is a passive optical network (PON) including an optical line terminal (OLT) <NUM> that is configured to interface between a set of networks, such as, for example, a public switched telephone network (PSTN) <NUM>, a wide-area network such as the Internet <NUM>, and a cable television network (CATV) <NUM>, and an optical distribution network (ODN) that includes fiber optic cables <NUM>, and passive optical splitters <NUM> and <NUM>. Providing data to the consumers of the ODN (e.g., LANs <NUM>(<NUM>)-(N)) are a set of optical network units (ONUs) <NUM>(<NUM>)-(N). Network nodes that provide packet traffic to and from the ODN (e.g., OLT <NUM> and ONU <NUM>(<NUM>)-(N)) provide switch processing of packets by determining whether a packet destination is on an associated network and on which input/output (I/O) ports of the network node the packet destination may be located. Differing data rates of LANs <NUM>(<NUM>)-(N) as compared with the ODN can result in congestion of data in the queues associated with the I/O ports coupled to those networks. As will be discussed more fully below, memory storing those port queues can require management subsequent to storing packet data on those queues should the queues suffer significant congestion.

It should be noted that while an ODN is used as an example of a network having devices that can incorporate embodiments of the present invention, other networks having differing line rate limitations can also have network devices incorporating embodiments of the present invention (e.g., WiFi, <NUM>, <NUM>, ethernet, and the like).

<FIG> is a simplified functional block diagram of a network node <NUM> (e.g., ONU <NUM>(<NUM>)-(N)) configured to implement embodiments of the present invention. Arriving network packets <NUM> arrive at network node <NUM> at a receive engine <NUM>. The receive engine can include interfaces to various media access control (MAC) clients (e.g., ethernet, GPON, NG-PON2, XG-PON, and the like). The receive engine is configured to receive an incoming data stream, reconstruct packets that are members of the data stream, and store those packets into internal memory <NUM>. The packet information is stored as members of queues that are stored using internal memory units (IMUs) <NUM>. An IMU is a fixed size memory unit (e.g., <NUM> bytes). IMU manager <NUM> manages a pool of IMUs <NUM>. IMU management includes, for example, receiving requests from client processes to acquire (e.g., when assembling a packet) and release (e.g., subsequent to transmission and eviction to the external memory) the IMUs.

A queue stored in internal memory <NUM> includes a linked list of packets (also known as frame descriptors), where each packet is stored as a set of IMUs. As will be discussed more fully below, the queue memory is managed by queue manager <NUM>.

Once stored, packets are made available to packet processor <NUM> for processing tasks. Such processing tasks can include, for example, determining an egress port and associated egress queue for the packet and performing forwarding actions associated with the egress queue; determining a quality of service (QoS) associated with the packet; performing access control list (ACL) operations; performing multicast operations; and the like.

In addition to allocating memory for received packets, IMU manager <NUM> monitors memory consumption in internal memory <NUM> to determine if the memory is becoming depleted (e.g., approaching or exceeding a predetermined threshold value). If the memory is becoming depleted, then IMU manager <NUM> can inform eviction dispatcher <NUM> of the depletion (e.g., providing an IMU depletion event). In some embodiments, IMU manager <NUM> can also manage allocation and recovery of external memory units <NUM> in external memory <NUM>.

As will be discussed in greater detail below, eviction dispatcher <NUM> can work with queue manager <NUM> to decide which queue stored in internal memory <NUM> is a candidate for moving some or all of the queue's contents to an external memory <NUM>. Once a candidate queue is identified, the eviction dispatcher informs eviction engine <NUM> which moves stored packets from IMUs <NUM> to external memory units (XMUs) <NUM> in external memory <NUM>. During this process, queue manager <NUM> can modify the identity of the packets in the queues to reflect the movement of the packet data from internal memory to external memory. When the egress port is ready to transmit the packet, queue manager <NUM> schedules a packet for transmission from a queue and notifies the transmit engine <NUM>. After the transmit engine transmits the packet, the packet's memory, either a set of IMUs or XMUs, is released to the IMU manager.

<FIG> is a simplified flow diagram illustrating an example process performed in data path flow <NUM> of a network node <NUM>, in accordance with embodiments of the present invention. A network packet (e.g., arriving packets <NUM>) is received at an ingress port (e.g., receive engine <NUM>) (<NUM>). The network packet is assembled and stored in an internal memory <NUM> (<NUM>) as a set of IMUs and enqueued to a packet job queue (<NUM>). When packet processor <NUM> is ready to process the packet, the packet is dequeued from the packet job queue (<NUM>) and then the processor performs packet processing (<NUM>). During packet processing, the processor determines the packet egress port (<NUM>) from which to send the packet along to the packet's destination and enqueues the packet to an egress port queue (<NUM>). When the egress port is ready to transmit the packet, the packet is dequeued from the port queue (<NUM>) and then provided to the egress port (<NUM>). The packet is then transmitted by a transmit engine <NUM> at the egress port as a departing packet <NUM> (<NUM>). Once transmitted, the packet memory (e.g., the set of IMUs) is released by, for example, the IMU manager.

Initially, the queued packet data is stored as a set of IMUs <NUM>. As will be discussed in below, the packet data can be moved from a set of IMUs <NUM> to a set of XMUs <NUM> prior to transmission from the egress port if internal memory <NUM> reaches a threshold capacity. Movement of the packet data from internal memory to external memory allows higher priority packets, which will soon be scheduled for transmission, to remain in quickly accessible internal memory, while providing a large, relatively inexpensive external memory store for lower priority packets, which will take a longer time to be scheduled for transmission.

<FIG> is a simplified flow diagram illustrating an example process performed in packet eviction flow <NUM> of a network node <NUM>, in accordance with embodiments of the present invention. IMU manager <NUM> monitors internal memory <NUM> for resource consumption and depletion. Packet eviction flow begins when the IMU manager detects a memory depletion event occurring in the internal memory (<NUM>). The memory depletion event can occur when the internal memory approaches a predetermined threshold of capacity (e.g., <NUM>% capacity). The IMU manager informs eviction dispatcher <NUM> of the depletion event (<NUM>). The eviction dispatcher then works with queue manager <NUM> to determine an egress port queue from which to evict one or more packets to XMUs <NUM> (<NUM>). A process for determining a queue from which to evict packets is described more fully below with regard to <FIG>.

Once a port queue is selected for eviction, the eviction dispatcher coordinates with the queue manager to determine which packets from that queue should be evicted from the internal memory to bring internal memory capacity down below a threshold value (<NUM>). This second threshold value may not be the same as that used to trigger eviction. The eviction engine then can acquire external memory resources (e.g., XMUs) for storage of packets, as those packets are being selected, and can copy the packet data from IMUs to the XMUs (<NUM>). This can be performed concurrently with the decision-making process for selecting the packets to evict, since the copying process can take longer than the selection process. During the selection and copying process, the identity of the queue entries can be modified to indicate that the data for the queue entry is moved or about to be moved to the external memory. Once the packet data is moved from IMUs to XMUs by the eviction engine, then the eviction engine releases the IMUs (<NUM>). If the internal memory depletion event is not cleared after removing the selected packets from the selected queue (<NUM>), then the process can continue with a selection of another queue from which to remove packets. Otherwise, if the event is clear (<NUM>), the process is complete until another internal memory depletion event is triggered.

Each egress port is allocated a set of queues. Embodiments of the present invention select queues from which to evict packet data from internal memory to external memory by determining which port to attack. For example, selection can be based upon the amount of time it may take to transmit all frames queued to that port. Once a port is chosen, then a queue associated with that port is selected (e.g., the lowest priority queue). An additional factor for queue selection is the amount of data (e.g., the number of bytes) stored in the queues associated with the selected port. For example, a port using a largest amount of IMUs is most eligible for selection of eviction of packet data to XMUs. Once a port is selected, a queue within that port is selected for eviction.

<FIG> is a simplified flow diagram illustrating an example of a process performed to select a queue from which to evict packets as part of the eviction flow illustrated in <FIG>, in accordance with the present invention. This process can be performed by the eviction dispatcher, the queue manager, or the eviction manager in conjunction with the queue manager. As discussed above, an egress port is selected from which to evict packets waiting for transmission (<NUM>). Selection criteria can include, for example, comparing a length of time that it would take to transmit all frames queued for the egress ports. Once an egress port is selected, the queue manager can find a lowest priority queue associated with the selected egress ports of the network node (<NUM>). While embodiments are discussed using priority of the queue for selection, other factors can enter into consideration for queue selection. For example, in light of internal memory eviction being a continuous process, a lowest priority queue may have previously had entries evicted from the internal memory. Thus, the entries remaining in the internal memory may be insufficient to reduce the internal memory capacity below the operating threshold. Since there is overhead in shifting from queue to queue for eviction, selecting a higher priority queue that has more entries residing in the internal memory can be more efficient than selecting a lower priority queue with an insufficient number of entries to reduce the IMU capacity sufficiently. So a determination is made as to whether the queue has a sufficient number of packet entries stored in the internal memory (<NUM>), where a sufficient number of entries is such that there is reduced hopping from queue to queue. If there is an insufficient number of entries, then a next lowest priority queue is found (<NUM>) and a similar evaluation is made as to whether there are sufficient entries stored in the internal memory (<NUM>).

Once a queue is selected to have packet entries evicted, a packet entry is designated to be moved to the external memory (<NUM>). Entries are chosen from the tail of the queue, since these are the entries likely to remain enqueued the longest before transmission. This also reduces the likelihood that an egress port will attempt to transmit the packet while the packet is in transition from IMUs to XMUs. When the packet is designated for eviction, the packet entry identifier can be revised to indicate that the packet data is stored in XMUs rather than IMUs (<NUM>). The designated packet entry information can then be provided to the eviction engine for moving the designated packet from the internal memory to the external memory (<NUM>). In this manner, the eviction engine can perform the slower task of packet copying while the process of designating packets for eviction can continue.

A determination can then be made as to whether more packets need to be moved to meet the congestion threshold (<NUM>). If not, then a determination is made as to whether there is another available packet in the selected queue (<NUM>). If not, then a next lowest priority queue is found (<NUM>) and the process continues. If there is another available packet, then then that packet is designated to be moved to the external memory (<NUM>). When sufficient space has been designated for eviction from the internal memory to the external memory (<NUM>), then the designation process can end.

As part of the process above, queued packets that have been moved can include a flag that they are resident in the external memory, beyond a change in the queue entry identifier. This flag can be used to accelerate the process for determining whether a queue contains sufficient entries stored in the IMU to be a candidate for the eviction designation process. If too many queue entries are flagged, then that queue can be skipped and another queue selected. In addition, as packet data is moved, the amount of IMUs in internal memory being used by the port is decremented accordingly. This updated amount can then be used by the eviction dispatcher as a port selection criteria for a subsequent eviction mission.

Embodiments of the present invention provide a mechanism by which packet processor internal memory can be optimally utilized to store higher priority, lower latency packets during processing and queuing for transmission, while lower priority, higher latency packets can be stored in lower cost, but higher power consumption external memory should availability of the internal memory become depleted.

Because the apparatus implementing the present invention is, for the most part, composed of electronic components and circuits known to those skilled in the art, circuit details will not be explained in any greater extent than that considered necessary as illustrated above, for the understanding and appreciation of the underlying concepts of the present invention and in order not to obfuscate or distract from the teachings of the present invention.

The term "program," as used herein, is defined as a sequence of instructions designed for execution on a computer system. A program, or computer program, may include a subroutine, a function, a procedure, an object method, an object implementation, an executable application, an applet, a servlet, a source code, an object code, a shared library/dynamic load library and/or other sequence of instructions designed for execution on a computer system.

Some of the above embodiments, as applicable, may be implemented using a variety of different information processing systems. For example, although <FIG> and the discussion thereof describe an exemplary packet processing architecture, this exemplary architecture is presented merely to provide a useful reference in discussing various aspects of the invention. Of course, the description of the architecture has been simplified for purposes of discussion, and it is just one of many different types of appropriate architectures that may be used in accordance with the invention. Those skilled in the art will recognize that the boundaries between logic blocks are merely illustrative and that alternative embodiments may merge logic blocks or circuit elements or impose an alternate decomposition of functionality upon various logic blocks or circuit elements.

Thus, it is to be understood that the architectures depicted herein are merely exemplary, and that in fact many other architectures can be implemented which achieve the same functionality. In an abstract, but still definite sense, any arrangement of components to achieve the same functionality is effectively "associated" such that the desired functionality is achieved. Likewise, any two components so associated can also be viewed as being "operably connected," or "operably coupled," to each other to achieve the desired functionality.

Also for example, in one embodiment, the illustrated elements of network node <NUM> are circuitry located on a single integrated circuit or within a same device. Alternatively, network node <NUM> may include any number of separate integrated circuits or separate devices interconnected with each other. For example, XMU <NUM> may be located on a same integrated circuit as packet processor <NUM> or on a separate integrated circuit or located within another peripheral discretely separate from other elements of network node <NUM>. Receive engine <NUM> and transmit engine <NUM> circuitry may also be located on separate integrated circuits or devices. Also for example, network node <NUM> or portions thereof may be soft or code representations of physical circuitry or of logical representations convertible into physical circuitry. As such, network node <NUM> may be embodied in a hardware description language of any appropriate type.

Furthermore, those skilled in the art will recognize that boundaries between the functionality of the above-described operations merely illustrative. The functionality of multiple operations may be combined into a single operation, and/or the functionality of a single operation may be distributed in additional operations. Moreover, alternative embodiments may include multiple instances of a particular operation, and the order of operations may be altered in various other embodiments.

All or some of the software described herein may be received elements of network node <NUM>, for example, from computer-readable media such as internal memory <NUM>, external memory <NUM>, or other media accessible to the various modules such as queue manager <NUM>, IMU manager <NUM>, eviction dispatcher <NUM>, and eviction engine <NUM>. Such computer readable media may be permanently, removably or remotely coupled to a processing system such as network node <NUM>. The computer-readable media may include, for example and without limitation, any number of the following: magnetic storage media including disk and tape storage media; optical storage media such as compact disk media (e.g., CD-ROM, CD-R, etc.) and digital video disk storage media; nonvolatile memory storage media including semiconductor-based memory units such as FLASH memory, EEPROM, EPROM, ROM; ferromagnetic digital memories; MRAM; volatile storage media including registers, buffers or caches, main memory, RAM, etc.; and data transmission media including computer networks, point-to-point telecommunication equipment, and carrier wave transmission media, just to name a few.

A mechanism is provided to maximize utilization of internal memory for packet queuing in network devices, while providing an effective use of both internal and external memory to achieve high performance, high buffering scalability, and minimizing power utilization. Embodiments initially store packet data received by the network device in queues supported by an internal memory. If internal memory utilization crosses a predetermined threshold, a background task performs memory reclamation by determining those queued packets that should be targeted for transfer to an external memory. Those selected queued packets are transferred to external memory and the internal memory is freed. Once the internal memory consumption drops below a threshold, the reclamation task stops.

A computer system processes information according to a program and produces resultant output information via I/O devices. A program is a list of instructions such as a particular application program and/or an operating system. A computer program is typically stored internally on computer readable storage medium or transmitted to the computer system via a computer readable transmission medium. A computer process typically includes an executing (running) program or portion of a program, current program values and state information, and the resources used by the operating system to manage the execution of the process. A parent process may spawn other, child processes to help perform the overall functionality of the parent process. Because the parent process specifically spawns the child processes to perform a portion of the overall functionality of the parent process, the functions performed by child processes (and grandchild processes, etc.) may sometimes be described as being performed by the parent process.

For example, differing egress queue selection criteria can be utilized to determine which packet data can be moved to the external queue memory space.

The term "coupled," as used herein, is not intended to be limited to a direct coupling or a mechanical coupling.

Claim 1:
A method for storing and accessing queued packet data in a network device, the method comprising:
detecting depletion of available memory space in an internal memory of the network device, wherein
the internal memory (<NUM>) is associated with a packet processor (<NUM>),
the internal memory (<NUM>) stores network packet data from a plurality of network packets, and
the network packet data is stored as entries of one or more egress packet queues;
selecting an egress packet queue from which to evict one or more associated packets from the internal memory (<NUM>);
selecting one or more packets associated with the selected egress packet queue for evicting from the internal memory (<NUM>);
copying the selected packets to an external memory coupled to the packet processor (<NUM>);
releasing internal memory (<NUM>) resources associated with the copied packets; and
accessing an entry from an egress packet queue, wherein
packet data for the entry is retrieved from one of the internal memory (<NUM>) or external memory (<NUM>) in response to previously copying the selected packets to the external memory (<NUM>),
characterized in that selecting the egress packet queue further comprises:
selecting an egress port from which to evict packets, wherein a first subset of the one or more egress packet queues are associated with the egress port;
finding a lowest priority egress packet queue of the first subset of the one or more egress packet queues; and
determining whether the selected egress packet queue comprises packet entries consuming a sufficient amount of data in the internal memory (<NUM>) to increase the available memory space in the internal memory (<NUM>) above a second predetermined threshold.