Method and apparatus for numeric optimization of the control of a delay-locked loop in a network device

[0001] This application claims priority of U.S. Provisional Patent Application Ser. No. 60/499,615, filed on Sep. 3, 2003 and U.S. Provisional Patent Application Ser. No. 60/553,122, filed on Mar. 26, 2004. The subject matter of these earlier filed applications is hereby incorporated by reference.

[0002] 1. Field of the Invention

[0003] The present invention relates to devices, software applications and networks that utilize data that is sent or received over data communication or computer networks. In particular, the present invention is directed to management and use of memory in a network device to implement certain policies. The processor and methods described provide greater reliability in the use of external memory to process the data sent and received by the network device.

[0004] 2. Description of Related Art

[0005] As computer performance has increased in recent years, the demands on computer networks has significantly increased; faster computer processors and higher memory capabilities need networks with high bandwidth capabilities to enable high speed transfer of significant amounts of data. The well-known Ethernet technology, which is based upon numerous IEEE Ethernet standards, is one example of computer networking technology which has been able to be modified and improved to remain a viable computing technology.

[0006] Based upon the Open Systems Interconnect (OSI) 7-layer reference model, network capabilities have grown through the development of repeaters, bridges, routers, and, switches, which operate with various types of communication media. Collectively, with respect to the present invention, all of these may be referred to as network devices. Switches, as they relate to computer networking and to Ethernet, are hardware-based devices which control the flow of datagrams, data packets or cells based upon destination address information which is available in each packet. A properly designed and implemented switch should be capable of receiving a packet and switching the packet to an appropriate output port at the maximum speed capability of the particular network.

[0007] Referring to the OSI 7-layer reference model discussed previously, the higher layers typically have more information. Various types of products are available for performing switching-related functions at various levels of the OSI model. Hubs or repeaters operate at layer 1, and essentially copy and “broadcast” incoming data to a plurality of spokes of the hub. Layer 2 switching-related devices are typically referred to as multiport bridges, and are capable of bridging two separate networks. Bridges can create a table of forwarding rules based upon which MAC (media access controller) addresses exist on which ports of the bridge, and pass packets that are destined for an address which is located on an opposite side of the bridge. Bridges typically utilize what is known as the “spanning tree” algorithm to eliminate potential data loops; a data loop is a situation wherein a packet endlessly loops in a network looking for a particular address. The spanning tree algorithm defines a protocol for preventing data loops. Layer 3 switches, sometimes referred to as routers, can forward packets based upon the destination network address. Layer 3 switches are capable of learning addresses and maintaining tables thereof which correspond to port mappings. Processing speed for layer 3 switches can be improved by utilizing specialized high performance hardware, and off loading the host CPU so that instruction decisions do not delay packet forwarding.

[0008] In addition, there has also been pressure from the implementers of the computer networks to have network devices to mediate traffic on the computer networks that are extremely flexible and low cost. One aspect of this lower cost can be the use of external memory, i.e. memory that does not natively reside within the network device. A network device may use external memory, at least in part, to temporarily store data that is received by the network device. This allows for the external memory to be switched out, if needed, without requiring revamping of the chip that makes up the network device.

[0009] The interface between the network switch and the external memory becomes more important as the throughput for the external memory increases. For example, for external memory such as 200 Mhz Double Data Rate Synchronous Dynamic Random Access Memory (DDR SDRAM), the interface and the memory controller must be able to read and write data at that frequency. In the past, the level of precision with respect to the timing control elements did not have to be as greater to accommodate slower memory.

[0010] To accomplish this, a master Delay-Locked Loop (DLL) is used to set the number of delay taps and used to set a 90 degree phase difference that is required by the memory. This is desirable because the clock edge should be centered right in the middle of the window for the memory because that is preferred. The signal from the master DLL is sent to slave DLLs that are populated in the memory channels of the network device. Thus, one command center receives the clock signal, the same clock signal used by the memory, and the proper signals are then used for all of the memory channels. The signal the master DLL sends out, after performing the proper locking, controls up to a 32-bit delay tap in the delay line.

[0011] However, as discussed above, problems can occur with the DLL functioning when the memory has a higher throughput and detection and correction must occur at higher speeds. One such problem can occur in that the phase shift must be detected to determine if it is still 90 degrees. As time goes by, the voltages and settings in the network device may shift and other changes may occur. The DLL needs to react to its working environment and automatically change its settings accordingly. One issue is how often to update the slave DLLs. If the update were to occur at every clock cycle, the delay lines would have issues when changing from tap to the next tap. If the slave DLLs are not updated and reset before the next cycle, certain glitches may be introduced. In other words, things may not momentarily be set correctly. The glitches can potentially generate extra clock edges that would be very undesirable to the function of the device.

[0012] According to one embodiment of the invention, a method of setting a delay offset in slave Delay-Locked Loop (DLL) modules by a master DLL module is disclosed. The method includes determining whether a delay tap value needs to be adjusted based on a comparison with a reference clock signal, calculating a delay offset value to correct the delay tap value, repeating the determining and calculating steps a predetermined number of times and forwarding a representative value of the calculated delay offset values. The representative value is determined through a comparison between all of the calculated delay offset values obtained in the repeating step.

[0013] Additionally, the step of repeating the determining and calculating steps the predetermined number of times may include repeating the determining and calculating steps over a provided number of clock cycles of the reference clock signal and obtaining the representative value by averaging all of the calculated delay offset values during the provided number of clock cycles. The provided number of clock cycles may be between 32 and 64 clock cycles, or equal to 64 clock cycles.

[0014] In addition, the step of repeating the determining and calculating steps may be performed a sufficient number of times to remove effects of low frequency power supply instability from the representative value. Also, the determining, calculating and repeating steps may be performed in the slave DLL modules after the step of forwarding the representative value.

[0015] According to another embodiment, a delay offset module for setting a delay offset in slave Delay-Locked Loop (DLL) modules by a master DLL module is disclosed. The delay offset module includes determining means for determining whether a delay tap value needs to be adjusted based on a comparison with a reference clock signal, calculating means for calculating a delay offset value to correct the delay tap value, timing means for measuring a predetermined time period, holding means for holding multiple calculated delay offset values determined by the calculating means over the predetermined time period, representative means for obtaining a representative value of the held calculated delay offset values and forwarding means for forwarding the representative value.

[0016] According to another embodiment, a delay offset module for setting a delay offset in slave Delay-Locked Loop (DLL) modules by a master DLL module is disclosed. The delay offset modules includes an adjustment determiner for determining whether a delay tap value needs to be adjusted based on a comparison with a reference clock signal, a calculator for calculating a delay offset value to correct the delay tap value, a timer for measuring a predetermined time period, a holding memory for holding multiple calculated delay offset values determined by the calculating means over the predetermined time period, a representative value calculator for obtaining a representative value of the held calculated delay offset values and a forwarder for forwarding the representative value.

[0017] These and other variations of the present invention will be described in or be apparent from the following description of the preferred embodiments.

[0024] The present invention is directed, in one embodiment, to a network device that receives data and process that data and may forward that data onto a destination based on attributes of that data. A general schematic of the network device is illustrated in FIG. 1. The device has an address resolution module (ARL) 101 that provides support for Layer 2 (L2), Multicast (MC), Layer 3 (L3), Internet Protocol Multicast (IPMC) switching, as well as Trunking, through various tables and registers. The ARL is connected to elements of the network switch divided into different modules. The ARL is also connected through a bus made up of channels, with data transferred on the CPI bus, protocols transferred therewith on the CPE bus and the S bus which is a sideband bus and is used to transfer signals between portions of the network device.

[0025] The bus can provide connections between the Memory Management Unit (MMU) and other interface modules. The interface modules include Ethernet Port Interface Controllers (EPICs) 120–125, Gigabit Port Interface Controllers (GPICs) 110–113, Interconnect Port Interface Controller (IPIC) 103, and CPU Management Interface Controller (CMIC) 104. The above components are discussed below. In addition, a Central Processing Unit (CPU) can be used as necessary to program the network device with rules which are appropriate to control packet processing. However, once network device is appropriately programmed or configured, it operates, as much as possible, in a free running manner without communicating with CPU.

[0026] As discussed above, the network device can have two module IDs, with module id 0 covering the Gigabit Ethernet ports, the CMIC and EPICs 0 through 2 and with module id 1 covering the IPIC and EPICs 3 through 5. The device may support 16K MAC address with 256 Layer 2 multicast addresses and 4K VLANs. The device also may support 256 multiple spanning trees and 8 levels of Class of Service. The device also supports protocol based VLANs with priority fields and supports jumbo frames. It also supports Layer 2 Multiprotocol Label Switching (MPLS) and supports classification for multiple packet formats, including Ipv6, Ipv4, double tagged, HTLS, 802.1Q tagged, Ether II and 802.3.

[0027] The GPIC modules (110–113) can interface to the Gigabit ports and on the medium side it interfaces to the TBI/GMII or MII from 10/100 and on the chip fabric side it interfaces to the bus. Each GPIC supports 1 Gigabit port or a 10/100 Mbps port. Each GPIC performs both the ingress and egress functions. The EPIC modules (120–125) interface to the 10/100-Mbit Ethernet ports and on the medium side it interfaces to the SMII/S3MII and on the chip fabric side it interfaces to the bus. Each GPIC supports an Ethernet port. A standard 802.3u MIIM interface is supported to interface with PHY devices, a standard JTAG interface for boundary scan and an LED interface to control system LEDs.

[0028] The IPIC 103 module can interface to the bus on one side and a high speed interface, such as a HIGIG interface, on the other side. The high speed bus can be, for example, is a XAUI interface, providing a total bandwidth of 10 Gbps. The CMIC 104 block is the gateway to the host CPU. In it's simplest form it provides sequential direct mapped accesses between the CPU and the network device. The bus interface may be a 66 MHz PCI. In addition, an I2C (2-wire serial) bus interface may supported by the CMIC, to accommodate low-cost embedded designs where space and cost are a premium.

[0029] The device can also support metering, with a granularity of, for example, 64 kb/s, having bucket sizes between 4 k and 512 k. The device may also include counters based on packet number or bytes, with those counters being in-profile, out-profile or general purpose. The device also allows for rate limiting or shaping. The device includes Ingress per port rate limiting, where when the incoming bandwidth exceed a programmed threshold, the port can either send a pause frame or drop packets. The rate control is on a per port basis and support for Egress per port rate limiting.

[0030] Support may also be provided for rapid spanning tree protocol that may be deleted by the port and storm control on a per port basis. The network device may also support link aggregation, with, for example, 32 trunk groups, with up to 8 ports in a trunk group. Trunking is also supported across modules and the load may be distributed based on source MAC or IP address and/or destination MAC or IP address.

[0031] The packet buffer memory of the device may include external DDR SDRAM memory with a 128 data bit DDR SDRAM interface, configured as 4 independent channels according to several embodiments. Each channel can include 32 data bits and it own address and control signals. The network device supports 32 MB or 64 MB packet buffer memory size, X16 and X32 DDR SDRAM memory and 166 MHz to 200 MHz clock DDR SDRAM memory. For reliability and signal integrity, there is support for CRC16 on every pointer, CRC5 on every cell and CRC32 on every frame. There is also support for a packet aging mechanism based on packet time stamp.

[0032] A fast filtering processor (FFP) can be incorporated into the EPICs and GPICs, in order to accelerate packet forwarding and enhance packet flow. The FFP is essentially a state machine driven programmable rules engine. Filters are applied to packets received by the FFP, through the use of masks so that certain fields of a packet may be evaluated. The filters utilized by FFP are defined by a rules table, where that table is completely programmable by the CPU, through the CMIC. The actions taken based on the filtering of the FFP include 802.1p tag insertion, 802.1p priority mapping, IP TOS (type-of-service) tag insertion, sending of the packet to the CPU, discarding or dropping of the packet and forwarding the packet to an egress port.

[0033] The network device may also provide supports for differentiated services. The differentiated services may include metering, per ingress port and per flow, policing, per egress port, re-marking, including DSCP (IPv4 and IPv6) re-marking, re-marking based on inclusive or exclusive matches in the FFP, and classification based on incoming DSCP, and dropping, as a result of metering or filtering. A pulse may be used to refresh all meters across the network device, including ingress metering, FFP metering, egress metering and WFQ MMU meters.

[0034] There are several mechanisms for buffering of packets and advanced methods for controlling the flow of packets. These include cell-based Head Of Line (HOL) blocking prevention that is programmable and is based on the total packet memory used by each Class of Service (CoS) per port. Packet-based HOL blocking prevention is also programmable and is based on the number of packets per CoS queue for each port. These mechanisms also support tail drop for CNG for HOL of 25%, 50%, 75% and 100% and supports centralized per port HOL counter. The mechanisms may also address back pressure, per ingress port and per flow through the FFP. The latter includes pause frame support (symmetric and asymmetric IEEE 802.3x) and a jamming mechanism for half-duplex ports. A Weighted Random Early Detection (WRED) congestion control per CoS queue per port is also available. Random Early Detection is a congestion avoidance mechanism that takes advantage of TCP's congestion control mechanism. By randomly dropping packets prior to periods of high congestion, RED tells the packet source to decrease its transmission rate. Assuming the packet source is using TCP, it will decrease its transmission rate until all the packets reach their destination, indicating that the congestion is cleared.

[0035] Data passes from the ingress buffer 201-1, in FIG. 2, to a drop filter 202 that may drop the packet based on programmed criteria. The packet data then passes to an arbiter 203, that has its own random access memory 206. The arbiter controls access to the memory channels 205-1 and 205-2 where packet data is stored. The arbiter communicates with a free cell pointer module 204 that provides a pointer to the next available free cells in the memory. The arbiter also is in communication with the egress queue 208 and egress buffer 211 modules. The egress buffer receives the packet data when it is ready to be sent out on the CPE interface. The egress queue module is also in communication with a scheduler 209 that schedules which packets and in what order they are sent out. The scheduler also communicates with a weighted fair queue 210 module to assist in making scheduling decisions, where those decisions result in specific read requests being sent to the arbiter.

[0036] As discussed above, problems can occur with the DLL functioning when the memory has a higher throughput and detection and correction must occur at higher speeds. One such problem can occur in that the phase shift must be detected to determine if it is still 90 degrees. As time goes by, the voltages and settings in the network device may shift and other changes may occur. The DLL should react to its working environment and automatically change its settings accordingly. One issue is how often to update the slave DLLs. If the update were to occur at every clock cycle, the delay lines would have issues when changing from tap to the next tap. If the slave DLLs are not updated and reset before the next cycle, certain glitches may be introduced. In other words, things may not momentarily be set correctly. The glitches can potentially generate extra clock edges that would be very undesirable to the function of the device.

[0037] In order to avoid such issues, a single particular value need not be used and an intelligent process to determine the proper value may be employed. In addition, network device and its power supply respond dynamically to the core frequency of the assembly, but also respond to high and lower frequencies. DC ripple, occurring between 1 khz and 500 khz, can result in variations in voltages that effect the DLL. If the update of the slave DLLs occurs when ready and it takes in a value specific to that particular cycle and uses it for a certain number of cycles, there could other issues. If the value is not representative, i.e. updated with either a high or low value, then that can cause errors.

[0038] In order to address the above issues, the present invention acts to average the offset values to obtain a value that is representative to be used over many cycles. In certain embodiments of the present invention, the averaging occurs over 32 or 64 cycles. Thus, the averaging acts as a filter to provide values are that not representative of high or low frequency values, but rather are somewhere in the middle during the averaging time period.

[0039] This “ave” Block is added to the conventional DLL design to use a numerical method to determine the average setting during the interested period, i.e., 32 cycles or 64 cycles, etc. This, in fact, functions as a filter to “remove” the low-frequency power supply instability and its effect of DLL settings. In a DLL-DL system, where the DLL determines the setting, i.e., the number of taps the DL should use to set the delay, this “ave” block can provide a setting which is more stable. This block can be placed either in the DLL Block or in the DL block of the DLL-DL system.

[0040] FIG. 3 illustrates schematically a portion of DLL circuit according to one embodiment of the present invention. The clock signal is introduced at CLKP and CLKN and is converted by converter 301 into a master clock signal Mclk. The High_f input is used to tell the DLL whether it should be set up for high frequency operation. In some embodiments, this would be for frequencies above 200 Mhz. The master clock signal is output at C_out and input into the PFD module 302, the counter 304 and the averaging unit 307. The master clock is also input into the delay loop 303 which produces the 90 degree phase shifted signal. The S_sign and S_adj are used to signal the magnitude and polarity of the number of taps that should be shifted from the lock position, which is determined in the add/sub unit 306. The offset values are averaged 307 and the delay shift is forwarded by a forwarding unit 308 to the slave DLLs 309, with a value S_del that stipulates the amount of offset. Thereafter, the slave delay line receives an input In and the proper delay is applied.

[0041] FIG. 4 illustrates schematically another portion of the DLL circuit according to one embodiment of the present invention. The master clock signal, M_clk, is provided as an input, where a portion of the signal is delayed through a delay module 401. It is determined whether the DLL is operating in a high frequency mode, where the proper signal is then fed to the delay taps 403. The DLL output setting, Del_d, obtained as a result of the portion illustrated in FIG. 3 is used to select to modulate 404 the clock signal to produce the 90 degree shifted clock signal. Thereafter, the process is replicated with similar modules, 411–414, to produce the 90 degree phase shifted master clock.

[0042] The method of the present invention, according to certain embodiments of the present invention, is illustrated in FIG. 5. In step 501, it is determined whether the delay tap needs to be adjusted. If it needs to be adjusted, then it is determined whether the offset value is within range, step 502, and the reset is synchronized to the master clock, in step 503. Thereafter, a predetermined number of offset values are accumulated, in step 504, and the rounded average is sent to the slave DLLs, in step 505. It should be note that the process of obtaining an optimal setting value can take place in either the master DLL or in the slave DLLs.

[0043] The above-discussed configurations of the invention are made with respect to a delay-locked loop (DLL) module, where such a module may be utilized in a network device, such as a network switch. Such a module may be used in memory circuits, such a SRAM, DRAM and non-volatile memory. A DLL module, according to the instant invention, may be used in embedded control systems, programmable arrays or central processing units. Such a DLL module may be used in all types of semiconductor chips and in non-analog chips. The instant invention may also be used in any application where a clock needs to be shifted, inverted, locked or corrected. Such listed uses of a DLL module are not exhaustive and should be taken merely as examples.

[0044] The above-discussed configuration of the invention is, in a preferred embodiment, embodied on a semiconductor substrate, such as silicon, with appropriate semiconductor manufacturing techniques and based upon a circuit layout which would, based upon the embodiments discussed above, be apparent to those skilled in the art. A person of skill in the art with respect to semiconductor design and manufacturing would be able to implement the various modules, interfaces, and tables, buffers, etc. of the present invention onto a single semiconductor substrate, based upon the architectural description discussed above. It would also be within the scope of the invention to implement the disclosed elements of the invention in discrete electronic components, thereby taking advantage of the functional aspects of the invention without maximizing the advantages through the use of a single semiconductor substrate.

[0045] Although the invention has been described based upon these preferred embodiments, it would be apparent to those skilled in the art that certain modifications, variations, and alternative constructions would be apparent, while remaining within the spirit and scope of the invention. In order to determine the metes and bounds of the invention, therefore, reference should be made to the appended claims.