基于随机早期丢弃的处理电路以及处理方法

摘要

一种基于随机早期丢弃的处理电路，包含有调度器、基于随机早期丢弃的决定逻辑以及控制器。其中调度器是用来依据基于随机早期丢弃的操作调度来产生触发事件，其中该调度器耦接至软件接口，以及调度器中的基于随机早期丢弃的操作调度是通过软件接口来进行程序化。基于随机早期丢弃的决定逻辑是用来执行第一基于随机早期丢弃的操作，并据以产生第一随机早期丢弃决定。控制器是用来接收触发事件，并触发基于随机早期丢弃的决定逻辑以依据至少触发事件来执行第一基于随机早期丢弃的操作。本发明的加权随机早期丢弃操作的调度规划是基于软件可程序化调度，因此可改善加权随机早期丢弃操作调度的弹性。

说明书

技术领域

本发明所揭露的实施例关于在网络环境中避免壅塞，尤指一种基 于随机早期丢弃(random early drop，RED)的处理电路以及相关方 法，来依据基于可软件程序化调度所产生的至少一个触发事件(例如 基于时间的触发事件)来触发基于随机早期丢弃的操作(例如加权随 机早期丢弃(weight random early drop,WRED)操作)。

背景技术

一般来说，网络装置(例如交换机)具有封包缓冲器来缓冲从一 个或是多个封包源传送来的封包。该封包缓冲器可以是具有有限存储 大小的动态随机存取存储器(dynamic random access memory,DRAM)。 若是入口流量的整体行速率(line rate)(即数据速率)高于出口流量的 整体行速率(即数据速率)，抵达该封包缓冲器的封包数目会大于从该 封包缓冲器发出的封包数目。在最糟的状况下会造成该网络装置的该 封包缓冲器的壅塞。

要侦测和避免壅塞，故特别地采用一种避免壅塞的机制。举例来 说，可以采用一种粗略的封包丢弃机制(又称作去尾(tail drop)机制)。 然而，去尾机制是平等地对待所有端口(port)/队列(queue)的封包，且 不会分辨不同的服务级别。当封包缓冲器满载时，去尾机制便会启动 来丢弃所有端口/队列的新进封包，直到封包缓冲器满载的状况解除为 止。换句话说，封包缓冲器达到其最大容量之后，任何新进的封包都 会被丢弃。因此，当封包缓冲器已满且突然有一阵封包流量从一个或 是多个主机发送过来，该网络装置便会同时失去所有的输入封包，因 而导致封包传递的表现不佳。

一种改良的避免壅塞机制可以用来降低去尾机制的启动机率。举 例来说，一种加权随机早期丢弃(weighted random early drop,WRED) 机制可以在输出接口开始出现壅塞的征兆时选择性地丢掉封包。不过， 加权随机早期丢弃操作的硬件成本颇高。例如针对多个端口/队列，则 需要多个基于硬件的加权随机早期丢弃电路来计算加权随机早期丢弃 的决定。

发明内容

依据本发明的示范性实施例，提出一种基于随机早期丢弃的处理 电路以及相关方法，依据基于可软件程序化调度所产生的至少一个触 发事件来触发基于随机早期丢弃的操作(例如加权随机早期丢弃 (weight random early drop,WRED)操作)以改善上述问题。

依据本发明的第一示范性实施例，提出一种基于随机早期丢弃的 处理电路，包含有调度器、基于随机早期丢弃的决定逻辑以及控制器。 其中该调度器是用来依据基于随机早期丢弃的操作调度来产生触发事 件，其中该调度器是耦接至软件接口，以及该调度器中的该基于随机 早期丢弃的操作调度是通过该软件接口来进行程序化。该基于随机早 期丢弃的决定逻辑是用来执行至少一个第一基于随机早期丢弃的操 作，并据以产生第一随机早期丢弃决定。该控制器是用来接收至少该 触发事件，并依据至少该触发事件来触发该基于随机早期丢弃的决定 逻辑以执行该第一基于随机早期丢弃的操作。

依据本发明的第二示范性实施例，提出一种基于随机早期丢弃的 处理方法，包含有：通过软件方式来对基于随机早期丢弃的操作调度 进行程序化；依据该基于随机早期丢弃的操作调度来产生触发事件； 以及参考至少该触发事件来触发基于随机早期丢弃的决定逻辑来执行 至少一个第一基于随机早期丢弃的操作，并据以产生第一基于随机早 期丢弃的决定。

本发明的加权随机早期丢弃操作的调度规划是基于软件可程序化 调度。使用者可被允许依据任何触发条件及/或应用要求来定义加权随 机早期丢弃操作的顺序，因此可改善加权随机早期丢弃操作调度的弹 性。

附图说明

图1为本发明的加权随机早期丢弃处理电路第一示范性实施例的 方框示意图。

图2为本发明软件可程序化存储器的实施例。

图3为图2所示的软件可程序化内存中所存储的加权随机早期丢 弃操作调度的变化设计。

图4为本发明的加权随机早期丢弃处理电路第二示范性实施例的 方框示意图。

图5为本发明的加权随机早期丢弃处理电路第三示范性实施例的 方框示意图。

具体实施方式

在说明书及后续的申请专利范围当中使用了某些词汇来指称特定 的组件。所属领域技术人员应可理解，制造商可能会用不同的名词来 称呼同样的组件。本说明书及后续的申请专利范围并不以名称的差异 来作为区分组件的方式，而是以组件在功能上的差异来作为区分的准 则。在通篇说明书及后续的请求项当中所提及的“包含”是为一开放 式的用语，故应解释成“包含但不限定于”。另外，“耦接”一词在此 是包含任何直接及间接的电气连接手段。因此，若文中描述第一装置 耦接于第二装置，则代表该第一装置可直接电气连接于该第二装置， 或透过其他装置或连接手段间接地电气连接至该第二装置。

本发明的精神是在于使用共享的加权随机早期丢弃(weight  random early drop,WRED)硬件来针对多个监控的加权随机早期丢弃目 标(例如网络装置的网络端口或是网络装置的网络端口的队列)满足 多个加权随机早期丢弃计算要求。并据以实现一种低成本加权随机早 期丢弃机制。此外，加权随机早期丢弃操作的调度规划是基于软件可 程序化调度。使用者可被允许依据任何触发条件及/或应用要求来定义 加权随机早期丢弃操作的顺序，因此可改善加权随机早期丢弃操作调 度的弹性。举例来说，加权随机早期丢弃操作是基于由软件可程序化 调度所预先定义的预定时间区间来进行调度，而非基于无法预测到达 时间的封包来进行调度。因此，当端口/队列速率较高时，能够避免由 两个连续封包抵达时间之间的典型加权随机早期丢弃更新区间所造成 的误差。因此，本发明提供改善的加权随机早期丢弃设计，能够保持 加权随机早期丢弃的准确度同时降低硬件成本。除此之外，对于较不 拥塞的端口/队列，可以跳过其加权随机早期丢弃操作以降低功耗。

为了简洁起见，以下使用加权随机早期丢弃处理电路来作为范例 以说明本发明的技术特征。然而，应注意的是，相同的观念可以应用 在任何基于随机早期丢弃(random early drop,RED)，也称为随机早期 侦测(random early detection)或是随机早期抛弃(random early discard)， 的电路中。换句话说，在不悖离本发明的精神的前提之下，可以对“加 权随机早期丢弃”和“基于随机早期丢弃”进行变通和变化，且相关 的设计也都属于本发明的权利范围之中。

图1为本发明的加权随机早期丢弃处理电路第一示范性实施例的 方框示意图。加权随机早期丢弃处理电路100可以被用在网络装置， 例如交换机中。在此实施例中，加权随机早期丢弃处理电路100包含 有调度器(scheduler)102、控制器104以及加权随机早期丢弃决定逻辑 106。调度器102是用来依据加权随机早期丢弃操作调度SCH来产生 基于时间的触发事件TRG_T至控制器104。在示范性设计中，调度器 102可以仅使用存储装置来实现。请参考图2，图2为本发明软件可程 序化存储装置的实施例。软件可程序化存储装置200具有加权随机早 期丢弃操作调度201存储于其中，且可用来当作图1所示的调度器102。 加权随机早期丢弃操作调度201包含有复数个索引202，其中每一索引 都存储监控的加权随机早期丢弃目标的索引值。以图2中的调度设计 为例，每一监控的加权随机早期丢弃目标都是该网络装置的网络端口。 因此，调度索引中的索引值可以仅记录端口编号。具体而言，网络端 口可具有复数个队列在该封包缓冲器中。相同网络端口的不同的队列 是相关于复数个不同的服务，而相同服务的封包都会被存放在相同的 队列中。故当在一个时间区间(时段)内为所选的网络端口触发加权 随机早期丢弃操作时，加权随机早期丢弃决定逻辑106可产生加权随 机早期丢弃决定，其中包含有所选择的网络端口内所有队列的加权随 机早期丢弃计算结果。然而，此仅为说明用途，并非用于限制本发明。 又例如，该监控的加权随机早期丢弃目标是该网络装置的网络端口的 队列。图3为图2所示的软件可程序化存储装置200中所存储的加权 随机早期丢弃操作调度的变化设计。在此实施例中，加权随机早期丢 弃操作调度301包含有复数个索引202，其中每一索引都存储有网络端 口的队列的索引值。因此，调度索引中的索引值可单单记录端口编号 以及队列编号。因此，故当在时间区间内为所选的队列触发加权随机 早期丢弃操作时，加权随机早期丢弃决定逻辑106可产生加权随机早 期丢弃决定，其中仅包含有所选择的队列的加权随机早期丢弃计算结 果，且该设计也落入本发明的权利范围。

假设每一监控的加权随机早期丢弃目标都是网络端口，如图2所 示，软件可程序化存储装置200(即调度器)循环地读取并且输出索 引202中一个个索引值，进而在每一时段(例如图2中的T1、T2、…T14) 进行一次设定并且产生该基于时间的触发事件。因此，基于加权随机 早期丢弃操作调度201的设定，加权随机早期丢弃决定逻辑106会在 每一时段T1～T14间产生加权随机早期丢弃决定，以响应相对应的基 于时间的触发事件，其指定了该加权随机早期丢弃计算所对应的网络 端口。例如，加权随机早期丢弃决定逻辑106会在T1时段响应基于时 间的触发事件，执行目标为端口0的加权随机早期丢弃操作。当该网 络装置采用了该加权随机早期丢弃机制以避免壅塞时，应妥善地设定 该些索引值以使较高优先端口能够在调度周期(例如T1～T14)内分 配到较多的加权随机早期丢弃操作，以及较低优先端口能够在同一调 度周期(例如T1～T14)内分配到较少的加权随机早期丢弃操作。

另外，有一种可能是该网络装置的至少一个网络端口/队列较少被 使用来进行封包处理。例如电子邮件服务的封包流量一般较低，因此， 可以跳过此种较不会造成壅塞的端口/队列的该加权随机早期丢弃操 作以节省功耗。换句话说，对于较不壅塞的端口/队列来说，无论是否 收到封包，都绝不会触发加权随机早期丢弃操作。在示范性设计中， 至少一个特定队列或是至少一个特定网络端口的索引值可以被排除在 该加权随机早期丢弃操作调度之外。这样一来，便不会为了该至少一 个特定网络端口/队列进行加权随机早期丢弃操作的调度，并据以降低 所提出的加权随机早期丢弃操作电路的功耗。

如图1所示，调度器102是耦接至软件接口101，因此，加权随机 早期丢弃处理电路100允许调度器102中的加权随机早期丢弃操作调 度SCH通过软件接口101来程序化。网络装置的用户可以手动地依据 该网络装置的实际网络端口/队列条件来设定加权随机早期丢弃操作 调度SCH。举例来说，网络端口0以及网络端口1为高列速率端口， 故较为重要且应具有较高的优先权。如图2所示，可利用加权随机早 期丢弃操作调度201来将更多的加权随机早期丢弃操作排定给网络端 口0以及网络端口1。换句话说，网络端口0以及网络端口1的加权 随机早期丢弃操作的出现频率会高于其它优先权较低的网络端口(例 如端口2～端口11)。由于调度器102中的加权随机早期丢弃操作调度 201并非固定，可以基于该网络装置的实际操作条件来动态地调整加 权随机早期丢弃操作调度201，因而有弹性地达到避免壅塞的目的。

图1中的控制器104会接收调度器102所调度并输出的每一基于 时间的触发事件TRG_T，然后触发加权随机早期丢弃决定逻辑106以 执行相对应加权随机早期丢弃操作来反应当下的基于时间的触发事 件。换句话说，当受到控制器104触发时，加权随机早期丢弃决定逻 辑106会为监控的加权随机早期丢弃目标(例如网络端口或是一列) 执行加权随机早期丢弃操作，并据以产生加权随机早期丢弃决定(例 如针对网络端口的所有队列的多个加权随机早期丢弃计算结果，或是 针对网络端口的队列的单一加权随机早期丢弃计算结果)。该加权随机 早期丢弃决定会指出封包源是否应减少其传输率来减轻/解决壅塞的 问题。加权随机早期丢弃可以通过提早主动丢弃某些封包而不是等到 队列满载，来避免大量的封包被丢弃。因此，加权随机早期丢弃可允 许传输线全时充分地被利用。

在监控的加权随机早期丢弃目标是网络端口的队列的情况下，加 权随机早期丢弃操作可包含依据最小临界值Thresholdmin、最大临界 值Thresholdmax、最大封包丢弃机率Probabilitymax以及平均队列长度 Queueavg来计算封包丢弃机率Probabilitydrop，并且基于所计算出的封 包丢弃机率Probabilitydrop来做出该加权随机早期丢弃决定。该封包丢 弃机率计算可以用以下的方程式来表示。

平均队列长度Queueavg是从过去平均队列长度以及当前队列长 度所得到的加权平均(移动平均)。当控制器104接收触发事件(例如 在此实施例中的基于时间的触发事件)，控制器104会从电路组件(未 显示于图中)要求参数，包含有Queueavg、Thresholdmin、Thresholdmax 以及Probabilitymax，然后将所接收的该些参数提供给加权随机早期丢 弃决定逻辑106以用于加权随机早期丢弃的计算。由图2可以看出， 加权随机早期丢弃决定逻辑106规律地依据加权随机早期丢弃操作调 度201来执行监控的加权随机早期丢弃目标(例如网络端口或是队列) 所属的加权随机早期丢弃操作。如此一来便可避免两个连续抵达的封 包之间的由一加权随机早期丢弃更新区间所造成的常见误差。

图1所示的加权随机早期丢弃处理电路100是操作在基于时间的 触发模式，并得以利用共享计算硬件来实现加权随机早期丢弃决定逻 辑106，来在一个时段中针对监控的加权随机早期丢弃目标执行加权 随机早期丢弃操作。由于加权随机早期丢弃决定逻辑106是以时间分 割的方式来运作，因此并不需要专门设计多组计算硬件来针对多个监 控的加权随机早期丢弃目标分别执行加权随机早期丢弃操作。因此可 以显著地降低硬件成本。

应注意的是，图1所示的加权随机早期丢弃处理电路100仅供说 明用途。任何使用所提出的软件可程序化加权随机早期丢弃操作来规 律或周期性地产生基于时间的触发事件，以针对指定加权随机早期丢 弃目标(例如网络端口或是网络端口的队列)发出加权随机早期丢弃 操作的加权随机早期丢弃处理电路，都属于本发明的权利范围。举例 来说，本发明另提出混合式加权随机早期丢弃处理电路，其能够对接 收到的基于时间的触发事件以及接收到的基于封包的触发事件的至少 其中之一做出反应。

请参考图4，图4为本发明的加权随机早期丢弃处理电路第二示 范性实施例的方框示意图。加权随机早期丢弃处理电路400是混合式 加权随机早期丢弃处理电路。加权随机早期丢弃处理电路100和加权 随机早期丢弃处理电路400之间主要的差别是在于控制器404另可接 收基于封包的触发事件TRG_P。基于封包的触发事件TRG_P可以是 封包抵达事件或是封包发布事件。在基于封包的触发事件TRG_P是一 封包抵达事件的情况下，每次一个封包抵达监控的加权随机早期丢弃 目标(例如网络端口或是网络端口的队列)时，便会产生基于封包的 触发事件TRG_P。在基于封包的触发事件TRG_P是封包发布事件的 情况下，每次从一个监控的加权随机早期丢弃目标(例如网络端口或 是网络端口的队列)发布封包时，便会产生基于封包的触发事件 TRG_P。如上所述，调度器102会在调度时间区间(时段)中输出基 于时间的触发事件TRG_T。当在当前时段中基于封包的触发事件 TRG_P并未发生时，加权随机早期丢弃处理电路400的运作形同加权 随机早期丢弃处理电路100。也就是说，控制器404会触发加权随机早 期丢弃决定逻辑106来依据基于时间的触发事件TRG_T所定义的加权 随机早期丢弃目标信息(例如端口数或是队列数)以针对指定的加权 随机早期丢弃目标来执行加权随机早期丢弃操作。然而，当控制器404 同时接收到基于时间的触发事件TRG_T以及基于封包的触发事件 TRG_P时，控制器404会先处理基于封包的触发事件TRG_P并触发 加权随机早期丢弃决定逻辑106。举例来说，控制器404会直接忽略基 于时间的触发事件TRG_T，并且触发加权随机早期丢弃决定逻辑106 来依据基于封包的触发事件TRG_P所定义的加权随机早期丢弃目标 信息(例如封包目的信息)以针对所指定的加权随机早期丢弃目标执 行加权随机早期丢弃操作。

图5为本发明的加权随机早期丢弃处理电路第三示范性实施例的 方框示意图。加权随机早期丢弃处理电路500是另一种混合式加权随 机早期丢弃处理电路。加权随机早期丢弃处理电路100和加权随机早 期丢弃处理电路500之间主要的差别是在于控制器504和加权随机早 期丢弃决定逻辑506。在此实施例中，加权随机早期丢弃决定逻辑506 有两个可独立运作的加权随机早期丢弃操作单元。也就是说，加权随 机早期丢弃操作单元512是用来执行加权随机早期丢弃操作以产生加 权随机早期丢弃决定1；以及加权随机早期丢弃操作单元514是用来 执行加权随机早期丢弃操作以产生另一加权随机早期丢弃决定2。关 于控制器504，另备用来接收基于封包的触发事件TRG_P，其中基于 封包的触发事件TRG_P可以是封包抵达事件或是封包发布事件。由于 加权随机早期丢弃操作单元512和加权随机早期丢弃操作单元514能 够独立地运作，控制器504会依据基于时间的触发事件TRG_T来触发 加权随机早期丢弃操作单元512，并且依据基于封包的触发事件 TRG_P来触发加权随机早期丢弃操作单元514。具体而言，加权随机 早期丢弃操作单元512的操作就如同图1所示的加权随机早期丢弃决 定逻辑106，也具有和加权随机早期丢弃决定逻辑106相同的好处/优 点。

如上所述，调度器102会在调度时间区间(时段)内输出基于时 间的触发事件TRG_T，当同时接收到不同监控的加权随机早期丢弃目 标所属的基于时间的触发事件TRG_T以及基于封包的触发事件 TRG_P时，控制器504会通过分别触发加权随机早期丢弃操作单元512 和加权随机早期丢弃操作单元514来处理基于时间的触发事件TRG_T 和基于封包的触发事件TRG_P。因此，在相同时段中，加权随机早期 丢弃操作单元512会针对监控的加权随机早期丢弃目标(例如端口0) 做出加权随机早期丢弃决定，以及另一加权随机早期丢弃操作单元514 会针对另一监控的加权随机早期丢弃目标(例如端口1)做出另一加 权随机早期丢弃决定。然而当控制器504同时接收到相同监控的加权 随机早期丢弃目标(例如端口0)所属的基于时间的触发事件TRG_T 以及基于封包的触发事件TRG_P时，若是加权随机早期丢弃操作单元 512和加权随机早期丢弃操作单元514都试图对同一监控的加权随机 早期丢弃目标做出加权随机早期丢弃决定，便会造成冲突。为避免这 样的冲突状况发生，控制器504会忽略基于封包的触发事件TRG_P且 不触发加权随机早期丢弃操作单元514。换句话说，控制器504仅会处 理基于时间的触发事件TRG_T并触发加权随机早期丢弃操作单元 512。

本发明另提供一种基于随机早期丢弃的处理方法，包含有：通过 软件方式来对基于随机早期丢弃的操作调度进行程序化；依据该基于 随机早期丢弃的操作调度来产生触发事件；以及参考至少该触发事件 来触发基于随机早期丢弃的决定逻辑来执行至少一个第一基于随机早 期丢弃的操作，并据以产生第一基于随机早期丢弃的决定。其中该触 发事件是基于时间的触发事件。其中该基于随机早期丢弃的操作调度 包含有复数个索引，其中每一索引存储有监控目标的索引值；以及产 生该基于时间的触发事件包含有：周期性地在复数个时段中的每一时 段，一个一个地读取该些索引中的索引值来设定并产生该基于时间的 触发事件。在本发明的另一实施例中，基于随机早期丢弃的处理方法 另接收一基于封包的触发事件；并依据该基于时间的触发事件以及该 基于封包的触发事件的至少其中之一来触发该基于随机早期丢弃的决 定逻辑。其中该基于封包的触发事件是如上所述的封包抵达事件或封 包发布事件。举例来说，依据该基于时间的触发事件来触发该第一基 于随机早期丢弃的操作；以及依据该基于封包的触发事件来触发该第 二基于随机早期丢弃的操作。当同时接收到相同监控的目标所属的该 基于时间的触发事件以及该基于封包的触发事件时，仅会处理该基于 时间的触发事件来触发该第一基于随机早期丢弃单元的操作以避免冲 突。

以上所述仅为本发明的较佳实施方式，凡依本发明权利要求所做 的均等变化与修饰，都应属本发明的涵盖范围。