CN108616458B

CN108616458B - 客户端设备上调度分组传输的系统和方法

Info

Publication number: CN108616458B
Application number: CN201810583272.7A
Authority: CN
Inventors: C·马斯普特拉; P·波和玛; J·刘
Original assignee: Apple Inc
Current assignee: Apple Inc
Priority date: 2012-02-03
Filing date: 2013-01-28
Publication date: 2022-03-08
Anticipated expiration: 2033-01-28
Also published as: US8787169B2; US8767772B2; KR20160062189A; US8812005B2; US8787168B2; EP2786539B1; CN104081736A; US20130201843A1; CN104081736B; KR101623197B1; US20130201927A1; US8873394B2; TW201338470A; US20130201995A1; US20130201828A1; US20130203422A1; JP5893762B2; KR101670642B1; US9031094B2; CN108616458A

Abstract

本公开涉及客户端设备上调度分组传输的系统和方法。公开了一种用于在客户端设备上管理分组调度的计算机实现的方法。例如，该方法的一个实施例包括：接收将被传输的分组；将所述分组入队到在网络堆栈级的队列中；确定分组调度当前正在驱动级还是在网络堆栈级执行；如果调度当前正在所述网络堆栈级执行，则从在所述网络堆栈级的队列选择所述用于传输的分组；并且如果调度当前正在所述驱动级执行，则从在所述驱动级的队列选择所述用于传输的分组。

Description

客户端设备上调度分组传输的系统和方法

本申请是申请号为201380007685.6、申请日为2013年1月28日、发明名称为“客户端设备上调度分组传输的系统和方法”的发明专利申请的分案申请。

优先权要求

本专利申请涉及并要求2012年2月3日由Cahya Masputra等人提交的名称为“SYSTEM AND METHOD FOR INTELLIGENT NETWORK QUEUE MANAGEMENT”的美国临时专利申请61/595,003的权益，其公开内容以引用的方式全文并入本文。

相关专利申请的交叉引用

本专利申请涉及同时提交的转让给Apple的2012年9月15日由Cahya Masputra等人提交的美国专利申请13/620.920。

本发明的一个实施例涉及在客户端设备中管理数据网络通信。还描述了其它实施例。

背景技术

数据网络允许人们使用他们相应的网络“上”的客户端设备相互通信并从网络上的各种来源获得信息。例如，运行在用户的工作站或膝上型计算机中的Web浏览器应用程序可与Web服务器连接来下载网页。该连接可跨越网络的若干中间节点或跳跃，所述节点或跳跃可包括诸如路由器之类的专用计算机。这些设备可发现端节点之间的路由，通过这些路由它们可转发已被拆分为数据分组的消息。每个节点可被赋予一个唯一的或全球的地址，诸如互联网协议(IP)地址。互联网是为人熟知的全球性的交互网络，在其中计算机网络通过路由器相互连接。

计算机网络协议具有分层架构。通常，最上层包括由诸如Web浏览器的应用程序提供的功能性。正是该层，至少在端节点中，可通过网络来引发两台计算机之间的连接。因此，例如，用户可在其计算机上选择期望的网站。Web浏览器(运行于该计算机中)开始一个过程，该过程导致建立与所选择的网站相关联的服务器的连接。Web浏览器通过被称为互联网络协议群或传输控制协议/互联网络协议(TCP/IP)栈的一系列功能发送“向下” 请求。该协议栈通常在软件的高层中通过软件实现，经常作为在客户端设备中运行的操作系统(OS)程序的一部分。一旦将所选择的网站解析为 Web服务器的IP地址，所述服务器通过网络而接触并与Web服务器中实现的相似协议群的上层程序建立合适的连接。

为了使用该连接，用户计算机中的TCP/IP栈封装来自Web浏览器的请求消息，在本实例中，该请求消息为标识网页的请求。该消息可在其沿协议栈向下的过程中被包括网络访问层的若干垂直层多次封装。它最终到达客户端设备的最低层，即物理层(通常认为其为网络访问层的一部分)。

来自Web浏览器的消息当离开用户计算机的物理层然后在网络中通过一个或多个跳跃后到达Web服务器，并通过Web服务器的协议栈“向上”到达对应于Web浏览器的程序。然后，对应程序可通过收集所请求的网页的数据并将其经过已建立的连接发送回用户计算机，对消息作出响应。

将数据拆分为多个消息或分组，并以与发送请求消息类似的方式发送。应用程序可具有被用户的客户端计算机中的一个或多个处理器执行的若干应用或进程。每个单独的应用可生成不同类型的网络数据流量，它们可具有不同的分组损耗、延迟和流动弹性要求。以举例的方式，社交网络应用可通过网络传送控制数据、文本、音频和视频，它们中的每个都具有相对于上述变量的不同要求。尽管它们可能都共享用户计算机中的相同的低层网络资源，每个应用通常具有其自己的一个或一组端口来传送该数据。在当前的具体实施中，将每个客户端设备通过网络与特定目的节点(即另一个客户端或服务器)互连的路由器包括大型传输和接收缓冲区。因此，分组损耗很少或没有，并且通常允许客户端设备传输分组而不考虑流控制，导致路由器队列内的“缓冲膨胀”。诸如TCP的协议是基于检测到的分组损耗确定拥塞和修改传输速度的自校正协议。

当使用大型缓冲区减轻分组损耗时，TCP协议另外，在当前客户端方的具体实施中，对分组的缓冲发生在驱动级。TCP/IP栈只是将分组向下推送至驱动，并且驱动管理其自己的传输和接收队列。由于在客户端内的驱动级执行的大量缓冲(以太网驱动可在传输之前缓冲队列中的多达4000个分组)，网络堆栈不具有准确的网络/拥塞信息。因此，需要更智能的机制来执行客户端设备内的网络排队，在其中利用了使用在驱动层和网络堆栈层之间的反馈通道。

发明内容

一种用于在客户端设备上管理分组调度的计算机实现的方法。例如，该方法的一个实施例包括：接收将被传输的分组；将所述分组入队到在网络堆栈级的队列中；确定分组调度当前正在驱动级还是在网络堆栈级执行；如果调度当前正在所述网络堆栈级执行，则从在所述网络堆栈级的队列选择所述用于传输的分组；并且如果调度当前正在所述驱动级执行，则从在所述驱动级的队列选择所述用于传输的分组。

附图说明

本发明的各实施例以举例的方式进行说明，而不仅限于各个附图的图形，在附图中类似的附图标号表示类似的元件。应当指出，本公开中提到 “一”或“一个”实施例未必是同一实施例，并且这样的援引表示至少一个。

图1A-B示出根据本发明的实施例的具有网络堆栈的客户端设备的框图。

图2A-B示出根据本发明的实施例的两个方法。

图3A-B示出根据本发明的两个不同实施例的针对传输数据分组的网络堆栈和驱动之间的通信。

图3C示出根据本发明的一个实施例的客户端侧的软件架构。

图4示出示例性的发送器线程和示例性的开始器线程。

图5示出示例性的类队列实例和调度器。

图6示出服务类映射至队列实例的一个实施例。

图7示出服务类映射至队列实例的另一个实施例。

图8示出套接字流量类映射至服务类的实施例。

图9A示出具有内置QFQ调度器配置的一个实施例中链路共享分布的最坏场景。

图9B示出根据一个实施例的分组过滤器(PF)配置的实例。

图10A示出根据一个实施例的使用流哈希的流控制。

图10B示出一个实施例中排队算法使用的当前容器组和阴影容器组。

图11A-B示出根据本发明的两个不同实施例的针对接收数据分组的网络堆栈和驱动之间的通信。

图12示出示例性的工作循环线程、轮询器线程和DLIL输入线程。

图13示出根据一个实施例的示例性的线程数据集。

图14示出一个实施例中采用的应用编程接口(API)。

图15示出一个实施例中采用的多个具有API的服务。

图16示出客户端方数据处理设备的一个实施例。

图17示出客户端方数据处理设备的另一个实施例。

具体实施方式

本发明的一个实施例涉及用于对在客户端设备上执行的网络应用进行主动队列管理的计算机实现的方法。

图1A是客户端计算设备101的框图，在该客户端计算设备上可实现本发明的实施例。示出的客户端设备101执行多个应用105-107，该应用105- 107通过诸如互联网的网络150与服务器120-121和其它客户端设备122通信。服务器120-121可包括(以举例的方式且不限于)Web服务器、电子邮件服务器、即时消息服务器和文件服务器。在一个实施例中，应用105- 107调用网络堆栈102提供的网络应用编程接口(API)208，以访问网络堆栈102提供的网络资源。

本实施例的网络堆栈102包括队列管理逻辑115用于管理代表应用 105-107中的每个的多个网络队列110-112。网络堆栈中的分组调度器116 基于分组分类(下面将更详细地描述)调度将被传输至每个队列和从每个队列接收的分组。尽管在图1A中被示出为独立的模块，但应当理解，可将队列管理逻辑115和调度器116实现为单个的集成软件模块。

在一个实施例中，队列管理逻辑110-112管理的队列110-112中的每个包括用于存储所述发出网络分组(例如，TCP/IP分组)的发送队列和用于存储所述进入网络分组的接收队列。基于应用105-107中的每个的网络要求对应用105-107中的每个的发送和接收队列进行不同的管理。例如，不同的应用可具有不同的分组损耗、延迟和流动弹性要求，队列管理逻辑115对它们全部进行监控和管理。在一个实施例中，提前指定应用105-107中的每个的网络要求(例如，当应用通过API 108初始注册时)，并且队列管理逻辑115基于指定的要求管理针对该应用的网络分组。以举例的方式，网络浏览应用通常比实时视频聊天应用具有更高的延迟容忍。因此，网络浏览应用将和具有与实时视频聊天应用不同的指定服务级的不同的队列相关联。

在一个实施例中，客户端设备上安装的每个驱动150包括用于管理一组驱动队列151-153的队列管理逻辑155，它们中的每个可与不同的服务级相关联。此外，每个驱动可具有其自己的调度器160用于在驱动级执行分组调度，以及自己的队列管理逻辑155用于管理队列151-153。与网络堆栈 102一样，可将驱动队列管理逻辑155和驱动调度器160实现为单个逻辑模块(而不是如图1所示的独立模块)。在一个实施例中，每个驱动150可选择其自己管理分组调度(本文中称为“驱动管理”调度)，或依靠网络堆栈102的分组调度器116和队列管理逻辑115进行分组调度/排队。

以举例的方式，且不受限制，以太网驱动和蜂窝无线(例如，3G、4G) 驱动可依靠网络堆栈102的调度器116提供的分组调度和排队，而802.11n (Wi-Fi)驱动可使用驱动调度器160以管理分组调度和排队。在一个实施例中，Wi-Fi驱动实现无线多媒体扩展(WME)(还被称为Wi-Fi多媒体 (WMM)标准)，以根据语音、视频、尽力服务和后台四个优先级来调度网络流量。然而，本发明的基本原理并不限于任何特定的联网标准。

在一个实施例中，Wi-Fi驱动可以动态地在由驱动所管理的调度和网络层调度之间切换。例如，在支持WME的802.11n网络上，驱动可选择驱动级调度，但在802.11b或802.11g网络上，驱动可选择网络层调度。在一个实施例中，当使用网络堆栈管理的调度时，网络堆栈102可在分组准备好出队时通知驱动。然后驱动使分组出队并传输所述分组(下面将会进行更详细的描述)。

如图1A所示，与不考虑网络状态将分组从网络堆栈推送至驱动并在驱动中缓冲的现有具体实施不同，在发明的一个实施例中，提供了在驱动层150和网络堆栈102之间的连续反馈171。从驱动150至网络堆栈的反馈确保了网络堆栈102知道由驱动150所管理的通信链路的网络状态，并可基于该知识执行分组调度/排队。在一个实施例中，网络堆栈102基于检测到的网络状态智能地实现了如本文描述的分组调度和排队。相似地，从网络堆栈102发出的至驱动150的反馈信号将网络堆栈的传输/接收队列112 内的状态(例如，诸如当新分组准备好从特定的队列被传输时)通知给驱动。

如图1B所示，可针对一些通信信道在网络堆栈层采用调度，而针对其它通信信道(例如，上述的一些WiFi通道)在驱动层采用调度。具体地，在示出的实施例中，针对至服务器120和123以及客户端121的通信信道，分组调度可在网络堆栈层102执行，而针对至服务器122的通信信道，可执行由驱动所管理的调度。此外，如图1B所示，单个应用105可具有赋予支持不同分组损耗、延迟和流动弹性要求的不同队列的不同类型的数据流量。例如，特定的应用可打开TCP/UDP套接字来传送控制数据、文本、音频和视频，它们中的每个都具有对于上述变量的不同要求。因此，一种类型的数据(例如，控制数据)可在与第一服务类相关联的队列113中排队，而第二类型的数据(例如，交互视频)可在与第二服务类相关联的队列110 中排队。另外，不同的应用可将数据在与相同服务类相关联的同一个队列中排队。例如，应用105和106可将控制数据在与针对控制数据的服务类相关联的队列110中排队，并且应用106和107可将交互视频数据在与针对交互视频数据的服务类相关联的队列111中排队。

另外，应当理解，根据网络连接性(例如，客户端101是否连接到以太网或Wifi)和其它网络变量，客户端设备101可在仍符合本发明的基本原理的情况下只使用网络层队列管理和/或调度或驱动管理的队列管理和/或调度。

图2A示出根据本发明的一个实施例的方法。在201，在客户端设备的协议栈的网络层接收将被传输的分组。如果在202处确定分组与使用由驱动所管理的调度的网络链路相关联，则在203处将分组提供给驱动层。驱动层接下来在204处对分组进行排队、调度和传输。然而，如果分组与在网络层执行分组调度的网络链路相关联，则在205处，网络堆栈将分组进行排队和调度以进行传输。在206处，在分组准备好被传输时通知驱动，并且在207处，驱动传输所述分组。

客户端计算设备101可以是台式计算机、笔记本或膝上型计算机、视频游戏机或其它消费电子设备。在本文所述的一些实施例中，客户端设备101是可包括双向语音和视频、电子邮件通信和媒体回放功能的便携式无线设备。在本实例中，客户端设备101和服务器之间的通信路径具有客户端设备101和无线基站(例如，蜂窝塔或Wifi接入点)之间的无线区段。在互联网参考模型中，客户端设备101的网络堆栈102根据任何合适的无线通信网络访问协议通过基站与网络接入网关通信，下面给出了无线通信网络访问协议的一些实例。可通过其它基站和网关的组合来访问其它客户端设备122。在网络访问层的上方是网络互联层(例如，为网络上的每个节点定义互联网协议(IP)地址)、传输层(例如，执行主机对主机的流控制、以及打开和关闭连接的传输控制协议(TCP))，和应用层(例如，应用程序及诸如HTTP、SMTP和SSH的进程协议)。

图2B示出使用由驱动所管理的调度或网络堆栈管理的调度传输分组的本发明的一个实施例。在251处，特定应用通过打开的套接字连接生成将被传输的分组。例如，交互视频应用可生成将被传输给另一个客户端的视频分组。在252，网络层基于分组的类型将所述分组在指定的服务类中排队。例如，如下所述，10种不同的服务类可被定义为针对10种不同的数据流量类型的队列数据。因此，如果分组是交互视频分组，可以将其在针对交互视频的服务类队列中排队。类似地，如果分组包含控制数据，可以将其在针对网络控制的服务类队列中排队。

不管将分组如何排队，可以将其根据驱动或网络堆栈管理的调度进行不同的出队。对于在254确定的由驱动所管理的调度，驱动可在255处执行从指定的服务类的出队操作。例如，如果驱动实现802.11n，则其可选择使用WMM定义的四种服务类执行调度(参见例如图7，其示出服务类和队列实例之间10:4的映射)。作为另外一种选择，对于其它的网络接口类型(例如，以太网、3G等)，可在网络层执行调度(参见例如图6，其示出服务类和队列实例之间1:1的映射)。因此，在260处，网络层执行所选择的服务类的出队操作。在270处，将分组提供给驱动层，该驱动层在271 处传输分组。

因此，从以上可看出，在一个实施例中，当需要传输分组时，将分组传送到针对网络接口配置的网络层调度器中。调度器从分组中提取服务类；服务类确定分组入队的队列实例。接下来分组入队至相应的队列实例；当队列已满或进行流控制时，可将分组丢弃(如下所述，由队列规则/算法(例如SFB)决定丢弃/入队)。通知驱动有工作要做。在某一时刻，驱动将分组出队。需要识别队列实例。如果接口被配置为针对“网络堆栈调度”，调度器选择要服务的符合条件的队列。如果接口被配置为针对“驱动调度”，则驱动向调度器指出被选择进行服务的队列。一旦识别了队列实例，将分组(如果可用)从队列出队。接下来将分组传送至驱动以通过传输分组的介质进行传输。

如图1A-B所示，在一个实施例中，连续的反馈172由网络堆栈102向应用105-107中的每个提供(如虚线箭头所示)并用于向应用105-107中的每个的发出/接收的网络流提供流控制。例如，当针对特定TCP或UDP套接字的传输队列110-112已达到指定的阈值时，生成反馈信号来指示相应的应用105-107以挂起或减少新分组的传输。

图3A-B示出根据本发明的不同实施例的不同网络驱动模型。在图3A 中，应用301使将被传输的分组传输至网络堆栈302(1)，该网络堆栈则将网络分组发送至驱动(2)的IO网络接口303。在一个实施例中，IO网络接口303对分组进行分类，并基于分组的分类(3)将分类的分组放置在合适的IO输出队列304中。(如上所述，对于WMM，分类可包括语音、视频、尽力服务和后台。驱动305接下来使用其自己的分组调度器将分组从合适的IP输出队列304(4、5)出队。

在图3B所示的网络堆栈管理模型中，应用301将被传输的分组发送至网络堆栈302(1)，该网络堆栈302则对分组进行分类(使用下面描述的分类方案)，并将分类的分组放置在合适的发送队列306中(2)。在一个实施例中，不同发送队列306的数量与分组分类的数量一样多(例如，10 个发送队列用于10个不同分组分类)。当队列中的一者中一个新分组准备好传输时，网络堆栈302通知驱动层(3)。驱动307的IO网络接口接下来使分组出队并将出队的分组传送至驱动305进行传输(5、6)。

图3C示出网络层102的另外的架构细节，包括用于对分组进行分类的分组分类器202、用于与应用201交接的API 203、网络分组层206、传输层205(例如，TCP、UDP)和套接字层204、用于调度分组传输的分组调度器209、多个类队列210、流建议模块207和内核编程接口(KPI)211。下面更详细地描述这些组件中的每个。

A.内核编程接口

在一个实施例中，采用了下述私用KPI集：

ifnet_allocate_extended()

分配支持新输出模型的ifnet实例。这是公用ifnet_allocate()KPI的扩展(私用)版本，其要求由调用者填充新定义的ifnet_init_eparams结构。该结构与ifnet_init_params类似，具有与新输出模型相关的若干新域：

ifnet_enqueue()

将分组入队至实现新驱动输出模型的接口的输出队列。其为实现 pre_enqueue()回调函数的驱动/群提供。

{ifnet_dequeue,ifnet_dequeue_multi}()

将一个或多个分组从实现新驱动输出模型并将调度模型设定为“正常” 的接口的输出队列中出队。

{ifnet_dequeue_service_class,ifnet_dequeue_service_class_multi}()

将一个或多个分组从实现新驱动输出模型并将调度模型设定为“驱动管理”的接口的输出队列中出队。

ifnet_set_output_sched_model()

将调度模型设定为“正常”或“驱动管理”。

{ifnet_set_sndq_maxlen,ifnet_get_sndq_maxlen}()

设定和获取输出队列的最大长度。

ifnet_get_sndq_len()

获取输出队列的当前长度。

ifnet_start()

触发实现新驱动输出模型的接口上的在驱动层的传输。其会导致引用驱动的start()回调函数，如果该回调函数还未被引用的话。

{ifnet_set_bandwidths,ifnet_bandwidths}()

设定和获取接口的上行/下行链路速率。在附接ifnet后，每当其层上有该信息时，驱动可在任何时间设定速率。

{ifnet_transmit_burst_start,ifnet_transmit_burst_end}()

当驱动不容易从硬件获得上行链路速率信息时，用于估计上行链路速率的替代机制。其将突发的传输的开始和结束通知给网络堆栈。

在一个实施例中，用IFEF_TXSTART标记来标记已将自己注册为支持新输出模型(即网络堆栈管理的调度)的驱动。

B.数据链路接口层(DLIL)208

开始器线程402(图4示出的一个实施例)

支持新输出模型(即网络层调度)的接口使用专用的内核线程“开始器线程”402，其功能是引用驱动的start()回调函数。在一个实施例中，作为将分组通过ifnet_enqueue()入队的过程的一部分，每当调用ifnet_start()时，通知该线程运行(如果其还没有运行的话)，从而允许应用线程在将分组入队至输出队列时立即返回。其为驱动的start()回调函数提供了序列化形式，从而使出队顺序地发生。其还减少了驱动层的复杂性，因为由于网络堆栈在该开始器线程的环境下执行驱动的start()回调函数时没有进行任何的锁定，驱动可执行某些随时阻断线程的执行的操作而不考虑太多影响(硬件相关或非硬件相关)。

令牌桶调节器

另外，当为接口配置了令牌桶调节器(TBR)时，网络层管理输出模型在ifnet层允许某种形式的上行速率限制。默认情况下，接口不配置TBR；需要通过ifconfig(8)或pfctl(8)手动配置以启用TBR。当TBR启用时，如图 4中的402所示，每当输出队列不为空时，开始器线程将周期性地唤醒(每 10ms)。在每个周期期间，允许驱动使与可用的令牌相同数目的字节出队；在每个周期的开始将令牌再次充满。根据TBR被配置的速率计算令牌的数目。一个特定的TBR具体实施无需要分配调出(与BSD使用的方法不同)；因此，由于固定了间隔进而与调出分辨率无关(可在不同平台上达到 10ms)，其可适应非常高的速率(几十千兆字节每秒)，而具有非常低的 CPU利用率。

传输队列(图5中示出的一个实施例)

ifnet的if_snd成员保存接口的传输队列。该数据结构包含关于内置调度器(类型、实例、回调函数)、TBR、以及任选地另选调节器的信息。

默认情况下，在一个实施例中，系统创建分组调度器的内置实例(ifcq 实例)。如所提及，分组调度器及其参数的选择取决于网络接口的类型，并在一些情况下还取决于网络的拓扑结构。在一个实施例中，当附接分组调度器时，分组调度器将其实例存储至ifcq_disc，并将enqueue(),dequeue() 和request()回调函数配置至调度器对应的程序。对于需要“由驱动所管理的” 模式的接口，可附接专用的调度器，该调度器提供dequeue_sc()替代 dequeue()回调函数。下面示出了这些回调函数的一些实施例：

调度器116的一个实施例将N个类实例化；每个类相关于服务类并管理队列实例110-112。根据分组如何被分类，将分组入队到这些队列实例的一个中。当配置了PF_ALTQ支持时，可通过分组过滤器(PF)基础结构 (例如，通过pfctl(8))覆写内置调度器及其参数。其提供了方便的方式来模拟分组调度的不同特性(例如，尝试不同的调度器和/或参数)。

分组调度器116

分组调度器模块116的一个实施例提供了将分组入队至其类队列实例 210中的一个或从中出队的入口点。在一个实施例中，每个类对应于一个队列。其根据调度算法和参数管理其所有的队列。

在一个实施例中，通过下述技术中的一个来配置调度器116并将其附接至ifnet：

1.内置(静态)：当接口附接至网络堆栈时，基于驱动请求的队列调度模型来选择调度器。对于“正常”模式，栈创建具有10个类 (从而队列)的调度器。相反地，对于“驱动管理”模式，创建具有 4个类的专用调度器的实例。

2.PF(动态)：在一个实施例中，可通过PF框架配置调度器及其参数来覆写内置(静态)配置。其要求启用PF_ALTQ配置选项，且选择“altq＝1”boot-args NVRAM选项。在一个实施例中，其在默认情况下不启用/允许。然而，当启用时，其允许方便和适宜的机制来试验不同的调度器和参数。

在一个实施例中，下列调度器在默认情况下不使用并仅在PF中可用：

在一个实施例中，在默认情况下(即，在网络堆栈层102)使用下列调度器：

映射

1. 1:1映射

如图6所示，一个实施例中用于网络层管理调度的QFQ配置分别提供了分组服务类601-610和分组队列实例611-621之间的1:1映射。如图所示，10个服务级大体上分为4组：630、640、650、660，并且为每组提供了优先次序。组基于有关延迟容忍(低-高)、损耗容忍(低-高)、弹性相对于非弹性流、以及诸如分组大小和速率的其它因素的分类流量特性定义。如本文所述，“弹性”流需要相对固定的带宽，而“非弹性”流可接受不固定的带宽。示出的1:1映射允许网络堆栈实现对每个服务类的行为和差异的全面控制：根据分组如何分类，将分组直接入队至队列中的一个；在出队期间，调度器确定来自最合适的队列的将被传输的分组。

2. 10:4映射

如图7所示，一个实施例中的用于由驱动所管理的调度的TCQ配置提供了10个服务类601-610与4个队列实例701-704之间的10:4映射。该调度器为被动的，意味着其不执行任何分组调度，而相反仅提供队列实例并将服务类映射到队列。由于该实施例中网络堆栈对调度没有控制，不能用与1:1映射类似的特性来定义队列。相反，可以被认为它们具有从低(L) 至最高(H+)范围内的优先级。将分组直接入队至代表分组初始分类的服务类的一个队列中。在出队期间，驱动负责选择最合格的用于传输的服务类。队列的数量被设定为4且为具体实施的产物；如所提及的，其还恰好是802.11WMM访问类别的数量。

排队原则

在一个实施例中，排队原则或算法模块管理类队列的单个实例；队列仅由一个或多个分组组成(mbufs)。算法负责确定是将分组入队还是丢弃。

在一个实施例中，通过下面的方法中的一个来配置排队算法并将其附接至调度器类的实例：

1.内置(由网络堆栈管理)：当作为在ifnet上配置分组调度器的一部分来实例化调度器类时，选择排队算法。调度器的所有类共享相同的队列算法(每个具有其自己独特的实例)。

2.PF(被动态或驱动管理)：作为另外一种选择，可通过分组过滤器(PF)框架来配置调度器及其参数(包括针对类的排队算法)，从而覆写内置(静态)配置。

算法

在一个实施例中，下列排队算法在默认情况下不使用，而仅通过PF可用：

对分组的分类

如所提及的，在一个实施例中，将每个出站的分组入队至对应于分组的服务类的类队列实例。服务类赋值，或分组分类，发生在整个网络堆栈的若干位置。一般来讲，分组分类可以是显式的(由应用选择)或隐式的 (由系统设定或覆写)。

显式分类：在一个实施例中，应用可使用下述在图8中示出的映射至服务类的流量服务类值中的一个，通过选择SO_TRAFFIC_CLASS选项 (通过setsockopt(2)固定地选择或通过sendmsg(2)每个消息地选择)对其流量进行分类：

因此，从以上可以看出，在一个实施例中，系统赋予网络控制分组最高优先级分类，从而确保控制分组在所有具有较低分类的分组前转发。这是对现有系统的改进，在现有系统中，某些控制分组(例如，诸如TCP确认字符(ACK)分组)可在队列中卡在其它类型的非控制分组后(从而降低了系统性能)。

在一个实施例中，当客户端设备上发生语音通话时，在队列中挂起任何被分类为后台系统启动(SO_TC_BK_SYS)的分组。因此，该实施例与现有系统比较具有显著的优势，在现有系统中，由于传输低优先级分组(例如，后台系统启动分组)，语音通话会劣化或掉线。因此，在本实施例中，要备份至服务(例如，诸如iCould)的用户的图片流或其它数据将不会干扰语音通话。

系统的一个实施例可阻止标记为后台系统启动的流量，使得它们不会干扰来电，从而提高了通话的可靠性。当启动电话呼叫时，网络层(例如， TCP/IP层)将会接收流控制通知以挂起所有的后台系统启动的流量。作为响应，网络层可停止向接口发送任何更多的分组。其还可中止向网络堆栈写入任何更多数据的应用。由于应用处于静止，其将帮助改善CPU利用率，并且其还会改善语音通话的可靠性。如果语音通话在合理的持续时间中完成，应用可恢复数据通信。

在一个实施例中，当挂起特定的低优先级应用时，网络堆栈102会 (周期性地)探测通信链路(例如，通过反馈信号171)来确定其可何时恢复传输并将该信息传送给相应的应用。当链路不再有负载时，就会恢复分组传输。

概括地说，驱动层150和网络堆栈102之间连续的流控制反馈171，以及网络堆栈和应用105-107之间的反馈172提供对网络通道和带宽的更智能、有效的分配。

在一个实施例中，上述值不代表保证，而更多的是应用向系统发出的关于其流量特性的提示。系统将基于流量的分类尽量提供关于流量的一些形式的差异，但由于在分组调度参数到网络拓扑或媒体状态的范围内的变化的因素，不能给出保证。

在一个实施例中，由与上述值的一个相关联的套接字生成的流量可在队列/缓冲(mbuf)中携带相应的服务类值；如图8所示，SO_TC值和 MBUF_SC值之间存在1:1的映射。

图9A示出一个具有内置QFQ调度器配置的实施例中链路共享分布的最坏场景。除了套接字级的分类，整个内核的一些地方使用 MBUF_SC_CTL服务类来分类某些控制类型的分组(例如，ARP、ND NS/NA、IGMP/MLD)。其还包括暂时提高TCP ACK使用的服务类。

隐式分类：该形式的分类可通过分组过滤器(PF)框架实现。其允许通过PF来安装分类规则，并对所有IP流量生效而不考虑它们在初始阶段是如何被初始分类的。已使用服务类相关关键字增强PF和pfctl(8)；图9B 示出PF配置文件的一个实例，其可被pfctl(8)处理以覆写内置设置。

因此，在显示分类情况下，应用通过默认的服务类(BE)打开套接字。应用可通过SO_TRAFFIC_CLASS套接字选项来设定套接字的服务类，从而所有将来的发送/写入操作均自动使分组以用相应的服务类来标记。应用可决定选择性地将每个发送至套接字的数据报与SO_TRAFFIC_CLASS辅助消息选项关联，从而使得关联的分组以相应的服务类被标记(但不影响其它当前或将来的分组)。在这种情况下，可容易地将该套接字与多个不同的服务类相关联。

在隐形分类情况下，将分类规则安装在分组过滤器引擎中。每个规则包含一个标记(例如协议、端口等)，在匹配时，其将会导致用服务类来标记分组。

分类标签。除了使用MBUF_SC值标记队列/缓冲(mbuf)外，在一个实施例中，执行分组分类202的模块还将一个或多个标签与分组相关联，以帮助系统的其余部分识别分组的类型或流。在一个实施例中，这些标签驻留于mbuf的内置的pf_mtag子结构内，并且不考虑如何进行分类(显式或隐式)来执行设定。下面列出了一个实施例中采用的标签：

标签	说明
		PF_TAG_FLOWHASH	流哈希已被计算并与mbuf相关联。
PF_TAG_FLOWADV	分组属于本地终止的可进行流建议的流。
		PF_TAG_TCP	最外层的分组使用TCP作为传输。

流反馈

流哈希：如图10A所示：在一个实施例中，用流哈希1001为每个通过接口发出的mbuf添加标签(从而使用PF_TAG_FLOWHASH标记)，这将帮助识别接口层上属于特定流的所有分组。在一个实施例中，流哈希1001 为32位整数，在下列地点中的一处计算：

1.套接字204。在一个实施例中，当连接套接字时，计算并存储套接字204的流哈希。接下来该套接字上的传输将导致在分组的mbuf 结构内携带哈希值。

2.分组过滤器(PF)。在一个实施例中，当分组进入驱动150，除非已将分组分类，在相关联的PF规则和状态中计算并存储流哈希。如果将分组成功地发送回IP 206，分组将在mbuf结构中携带关联于与其匹配的规则或状态的流哈希。

在一个实施例中，用于计算流哈希的哈希算法按照性能根据计算系统平台的不同而不同。下表示出示例性的平台和相应的哈希：

平台	哈希算法
		Intel 32位	MurmurHash3(32位，i386变体)
Intel 64-位	MurmurHash3(128位，x86_64变体)
		ARM等	32位JHash

流控制和针对TCP的建议：使用本文所述的队列管理技术，当在接口中排队的每流的分组数量到达上限时，对使用TCP发送的应用进行流控制。与使用例如显式拥塞通知(ECN)的指示器或分组丢弃不同，接口向传输层提供流建议反馈。其可以进行而不发生任何分组损耗。

当下列两个条件中的一个为真时，接收来自AQM连接的流建议：

1.TCP连接的发送速率增加而超过链路支持的带宽。

2.作为设备的第一个跳跃的无线链路的可用带宽下降。

在这两种情况下，发送更多的分组将在接口队列上积累分组并增加应用体验到的延迟。另外，这可能会导致丢弃分组，其由于TCP发送器必须重新传输这些分组而降低性能。通过使用流建议机制，TCP发送器可与可用带宽相适应而不会发生任何分组损耗或任何性能损失。接口队列将不会丢弃TCP分组而仅向连接发送流建议。由于该机制，显著地减少了设备驱动中的缓冲，从而改善了设备上所有TCP连接的延迟。

TCP连接对流建议的主要响应是减小其拥塞窗口，这实际上将减小其发送速率。这通过减少慢开始阈值和允许连接进入拥塞避免状态的方法进行。但是如果连接已在进行恢复，意味着连接已在该往返时间经历分组损耗并已降低其发送速率。在这种情况下，不会再进一步减小拥塞窗口。

流控制的连接将避免使套接字可写入，直到流控制解除。这将避免在应用无法在接口上向外发送分组时应用写入更多的可能只能缓冲在网络堆栈的数据。这将有利于只需要发送最新更新而宁可丢弃旧的更新的交互式应用。

在流控制状态下，当存在以重复确认字符或SACK信息形式接收的 TCP确认字符中的分组损耗指示时，连接将退出流控制并开始快速恢复以立即重新传输丢失的数据。这不会再增加延迟，因为恢复期间的分组发送的速率是限定的。由于保证接口不会丢弃任何TCP分组，连接将能够尽快地重新传输丢失的数据。

当连接处于流控制状态，意味着分组以比以前慢的速度离开接口。在这种情况下，有可能存在等待在接口队列中的准备好发送的分组。通常这些分组是上一个发送窗口的最后的分组。如果等待时间超过了连接上计算的重新传输超时，则启动超时。此时，重新传输已发送的数据可在接口队列创建同一分组的重复分组。其后这会生成重复的确认字符并导致连接不必要地进入恢复。

为了避免该混淆，流控制TCP连接将避免从重新传输定时器重新传输分组直到更晚的时间。如果等待时间过长，连接可超时退出而不会永久等待，并将错误返回至应用。

每当启动重新传输超时，后退计时器直到重新开始。这将有助于检测链路上延迟的突然增加。但是对于流控制的套接字，延迟可能是流被暂时阻塞的结果。当连接退出流控制状态，退回结束。这将有助于从此及时地启动重新传输计时器。

当接口队列的分组流出并且队列级降到阈值以下时，接口将生成流建议使所有被流控制的流重新开始发送数据。此时，TCP套接字也开始可写，并且应用开始写入数据。

当流控制解除，连接将发送以前从未被发送的新数据。这将生成新确认字符并启动ACK计时器。这还将有助于检测是否有未检测到的流控制之前的任何数据丢失。如果没有要发送的新数据，将很快启动重新传输计时器，其将触发任何未被确认的未发送的数据的重新传输。

使用流建议和流控制机制，TCP连接可适应链路带宽的变化并减小由在主机的多个级的缓冲分组引起的延迟。

流控制和针对UDP的建议：在一个实施例中，UDP套接字只有在使用系统调用connect()使其与对等对象连接的情况下，能够进行流控制。当接口队列中的UDP流的分组的数量超出了流控制的极限时，生成建议。此时将套接字标记为处于流控制。不同于TCP，接口队列将丢弃此后生成的所有UDP分组。套接字将不可写，意味着使用选择或轮询或kevent系统类的等待写事件的应用将不会获得该事件，直到流控制解除。如果应用强行向套接字写入数据，套接字层将丢弃分组并返回错误(ENOBUFS)。

这不同于先前的行为，在其中所有的UDP写入成功而只在其后由驱动丢弃分组。UDP流控制和建议将向应用提供即刻反馈从而使它们立即减小发送速率。例如，视频应用可改变其编码以通过网络发送较少的数据。

由于在流控制UDP套接字上将分组在套接字层丢弃，与先前一直处理并向驱动发送只能被丢弃的分组比较，节约了很多的CPU利用率。流控制的UDP流的其它优势在于其不会淹没接口。这将减少分组损耗并改善主机上的其它流的延迟。

在一个实施例中，由于使用随机公平Blue(SFB)(参见本专利申请的附录B)作为排队算法，使在接口层跟踪流成为可能。在一个实施例中， SFB的具体实施使用了2级布隆过滤器，由此流(如流哈希值1001所指示的)在每个SFB级1009中映射至恰好一个容器。本实施例的每个容器跟踪分组的数量以及流丢弃/标记概率。在一个实施例中，SFB还跟踪处于流控制下的流的列表。流控制和流建议的阈值基于容器分配(当前设定为队列极限的1/3)。相应地进行容器概率的更新，但当前不用于限速。

流挂起和恢复

在一个实施例中，当网络接口节流时，挂起某些被标记为“伺机”的套接字。在一个实施例中，当这些套接字生成的分组入队至受影响的队列时，将其丢弃。在一个实施例中，在套接字上将生成NOTE_SUSPENDED事件以通知应用无限期地阻塞套接字上的流量。然后，应用可决定是否退出连接。当接口不再节流，受影响的队列不再阻塞分组，并且将在受影响的套接字上生成NOTE_RESUMED事件。内部地，流控制可使用相同的机制，以及使用建议来实现挂起和恢复。

入站网络层调度模型

一个实施例中的伺机的轮询使用了如图11B所示的网络驱动输入模式。驱动组件1111针对要接收的分组对硬件1112进行轮询，并且IO网络接口 1110对驱动进行轮询。每个接收队列实例对驱动1111的IP网络接口1110 进行轮询(3)以确定是否有任何与该接收队列相关联的分组准备好出队 (3)并向上传递至网络堆栈1108(4)，以及随后向上至请求应用1107 (5)(其如(6)所示针对新分组对其相关联的接收队列实例1109进行轮询)。

因此，在该新模式下，入站的分组不再如图11A的1-6的操作所示，由驱动/群向上推入网络堆栈。相反，入站的分组驻留在驱动的接收队列 1109中，直到网络堆栈1108将其出队。在一个实施例中，这包括关闭客户端设备硬件的接收中断请求(IRQ)。所述实施例独特的一个原因是网络堆栈1108(结合驱动)根据负载系数，在轮询(图11B)和传统(图11A)模式下交替变换。在一个实施例中，当负载到达预定的阈值(例如，在驱动队列中积累的分组的指定水平)，系统可转入传统模式(图11A)。当转入传统模式时，打开硬件的接收IRQ，并且驱动1105通过网络堆栈1102 将分组从IO网络接口1104向上推动至合适的接收队列实例1103，并最终至请求应用1101。

内核编程接口(KPI)

在一个实施例中，为了适应上述配置，采用了一组私用KPI：

ifnet_allocate_extended()

分配支持新输入模式的ifnet实例，具有若干相关的域：

ifnet_input_extended()

除了驱动1111向网络堆栈1108提供所有与分组链的开始和结束相关的信息以及总分组和字节计数外，与ifnet_input()类似。因为其允许更好的效率，鼓励已具有该信息的驱动来使用该新变量。其使用与驱动是否采用了新模式(图11B)无关。

在一个实施例中，使用IFEF_RXPOLL来标记已将自己注册为支持新输入模式(图11B)的驱动。

数据链路接口层(DLIL)208

输入线程：在一个实施例中，在DLIL输入线程环境内的输入分组处理发生在整个网络堆栈中。一些接口具有它们自己的专用输入线程，而其它接口共享公用(主)输入线程。在一个实施例中，DLIL输入线程具有3 个变形：

1.主输入线程

在一个实施例中，由环回接口以及其它不具有自己专用输入线程的接口使用主输入线程(即，除了以太网/PDP或那些不支持RXPOLL以外的任何接口)。该线程还用来处理所有的协议注册和分组注入。其在 dlil_main_input_thread_func()中实现。

2.传统输入线程

在一个实施例中，传统输入线程由不采用RXPOLL模式的以太网/PDP 接口使用，其在dlil_input_thread_func()中实现。

3.RXPOLL输入线程

在一个实施例中，RXPOLL线程由采用RXPOLL模式的任何接口使用，其在dlil_rxpoll_input_thread_func()中实现。

轮询器线程

在一个实施例中，支持新输入模式(RXPOLL)的接口使用专用的内核线程“轮询器线程”(如图12中的1202所示)，其用来调用驱动的 input_poll()回调函数以从驱动获取一个或多个分组；其在轮询打开时进行，否则轮询器线程1202保持休眠。该线程与图12中的1201所示的工作循环线程类似，均以调用ifnet_input()结束，从而将分组存放至RXPOLL- capable DLIL输入线程的接收队列。

分组接下来在该DLIL输入线程的环境下沿网络堆栈向上发送以进行进一步的处理。

伺机轮询

在一个实施例中，RXPOLL-capable接口在 IFNET_MODEL_INPUT_POLL_OFF模式和IFNET_MODEL_INPUT_ POLL_ON模式之间转换。在一个实施例中，前者为默认/初始模式；当网络堆栈确定负载系数低时，其为接口选择该模式。当前通过检查DLIL接收队列中的分组和字节的EWMA(P__平均、B__平均)，以及DLIL输入线程唤醒请求的EWMA(W__平均)来确定负载系数。

参考图12中的DLL输入线程1203，在一个实施例中，当(P__平均≧ P_hiwat&&(B__平均≧B_hiwat||W__平均≧W_hiwat))，至 IFNET_MODEL_INPUT_POLL_ON的切换完成，其中P_hiwat、B_hiwat 和W_hiwat分别为针对分组、字节和唤醒请求的高水印值。相反地，当(P_ _平均≦P_lowat&&B__平均≦B_lowat&&W__平均≦W_lowat)，至 IFNET_MODEL_INPUT_POLL_OFF的切换完成，其中P_lowat、B_lowat 和W_lowat为针对所述变量的低水印值。

在一个实施例中，当前基于某些工作负载任意地选择这些低水印值和高水印值，并且它们应作相应地调整以适应未来的工作负载(以及变化的链路速度)。

在一个实施例中，混合的轮询逻辑体驻留于 dlil_rxpoll_input_thread_func()，其中基于上述逻辑通过调用驱动的 input_ctl()回调函数进行模式之间的转换。注意对转换进行限速，从而使它们不会进行得过于频繁(设定默认的保持时间为1秒)。

图12示出当关闭/打开轮询时，线程1201-1203之间的关系的一个实施例。

在一个实施例中，轮询关闭/打开模式的主要区别在于调用ifnet_input() 或ifnet_input_extended()的环境和频率。

在一个实施例中，当轮询关闭时，作为主机CPU进行对从硬件发出的接收IRQ处理的一部分调度工作循环线程1201；该IRQ向主机发送设备已传送一个或多个分组至主机(例如，通过DMA)的信号。无论硬件上IRQ 合并的级别如何，由入站分组的速率驱动对该IOKit工作循环线程进行调度的频率。与该调度(环境切换等)相关的代价非常巨大，特别是考虑到我们的系统架构将所有的IRQ传送至CPU0的情况。因此，在一个实施例中，当检测到高负载系数时，打开轮询。

当轮询打开时，工作循环线程1201由于关闭接收IRQ而保持静止。仍然将分组从设备传送至主机，并且它们积累在驱动1111的接收缓冲中，直到由网络堆栈1108通过input_poll()回调函数获取。现在活动的轮询器线程 1202，除了网络堆栈1108严格控制该线程获得调度的频率外，执行与工作循环线程1201等同的功能性。

在一个实施例中，考虑到分批处理与从介质接收的分组相关的每分组处理代价，轮询改善了性能。当轮询打开时，网络堆栈指示驱动进入轮询模式。在轮询模式，驱动关闭其与从硬件到达的分组的通知相关联的接收中断或陷阱处理器。除非不中断CPU，分组会一直到达主机存储器(从设备通过DMA或等同方式)。这将减少CPU的负载，因为每个中断通常将触发一系列工作来对其进行处理；并且其对于性能会有一些负面影响，因为其会抢占当时运行在CPU上的其它所有程序的资源。网络堆栈以1毫秒的间隔(默认情况下；该值可配置)进行轮询，并在每个间隔从驱动抽出分组。如果检测到分组速率降低，退出轮询模式并重新启动中断。

在一个实施例中，可采用轮询来减少电力消耗(例如，当在“低电力” 模式下)或基于用户活动(或不活动)进行轮询。例如，如果系统在低电力模式下，将该信息提供给网络堆栈，然后网络堆栈可选择在所有合适的网络接口上进入轮询模式。当系统不再处于低电力模式下时，则通知网络堆栈从而退出轮询模式。

对于使用活动，如果系统忙于处理用户接口输入，将该信息提供给网络堆栈，然后网络堆栈可选择在所有合适的网络接口上进入轮询模式。当系统不再忙于处理UI输入时，通知网络堆栈从而退出轮询模式。

接收队列

在一个实施例中，ifnet的if_inp成员保存针对DLIL输入线程1203的接收队列。在一个实施例中，数据结构具有如图13所示的信息。

不同于传输队列，接收队列与DLIL输入线程实例相关联而不是与接口相关联。如上所述，一些类型的接口共享通用(主)输入线程，而其它的接口具有自己的专用输入线程。另外与可以有至多N个传输队列的传输不同的是，当前每输入线程只有一个接收队列。该结构还保存有关于用来输入的实际内核线程、工作循环1201、以及轮询器线程1202的信息。在一个实施例中，所有的这些线程被配置为共享相同的线程依附性标签，从而在同一个处理器集中调度它们(为了更好的高速缓存局部性)。在一个实施例中，伺机轮询所需的参数(例如模式、{P、B、W}__平均、{P、B、 W}_{lo、hi}wat)同样驻留在该结构内。

链路事件

在一个实施例中，将与接口相关的事件从网络堆栈102发送至附接的调度器116和队列管理逻辑115，并进一步至所有的类队列实例110-112。这使得调度器、队列管理逻辑115和其类在需要时，相应的调整它们的参数。事件如下：

如上所述，本发明的实施例包括对两个不同调度模式的支持：(1)在网络堆栈层的调度和(2)在驱动层的调度。驱动可选择使用哪种类型的调度。在一个实施例中，如果驱动实现802.11n，其可选择使用WMM定义的 4种服务类执行调度(参见例如图7示出服务类和队列实例之间10:4的映射)，而如果驱动实现任何其它的接口(例如，102.11b/g、3G、以太网等)，其可选择在网络层执行的调度(参见例如图6示出服务类和队列实例之间1:1的映射)。

在一个实施例中，在驱动管理模式下，可按网络堆栈管理模式建立所有的队列，但通过驱动调度器160执行调度。因此，基于驱动的调度器接下来将基于优先级针对特定类对每个出队操作请求多个分组(即，使用针对WMM的4个类)。

尽管调度器116、160决定从中使分组出队的队列，由队列管理逻辑 115(还被称为“丢弃器”，因为其可选择丢弃或是入队分组)实现的排队算法决定在出队之前分组应入队的队列。在一个实施例中，调度器116将分组传递至队列管理逻辑115，由队列管理逻辑115决定是将分组丢弃还是入队。

如上所述，在一个实施例中，网络堆栈使用的调度器116使用快速公平队列(QFQ)而驱动调度器160使用流量类队列(TCQ)，上面已详细描述了它们中的每个。

流控制和SFB队列的其它细节

在一个实施例中，无论所选择的调度器的种类，使用相同的队列管理逻辑115。对于由驱动所管理的调度器160和网络级调度器116均可使用随机公平blue(SFB)作为由队列管理逻辑115实现的默认排队算法。如图 10A所示，流哈希使得在网络和驱动层两者内容易地跟踪来自不同流/套接字的分组，并由SFB算法使用这些分组。当初始连接套接字204后，计算、在套接字数据结构中存储、以及在连接的套接字204生命期内使用哈希值 1001。每当数据从套接字向下发送至低层(例如，传输层205、IP层206、发送队列306、以及驱动层150)，流哈希值1001随分组发送，并被用来唯一地识别套接字/流。当识别流后，当入队每个新分组时SFB容器1009 中的一个或多个内的计数器(图10A中由变量C标识)增加，当出队每个分组时减少。因此，已知每个流中当前排队的分组数，并用其来执行针对该流的流控制。在一个实施例中，如果特定流有超出指定的阈值排队的分组(在图10A中标识为计数器C>＝FADV THRESHOLD)，则增加一些针对该流的概率值。当概率到达其极限(例如，1)时，表示有太多的分组 (即应用发送过快)，丢弃接下来发送至该流的分组。

图10A详细示出该机制。在一个实施例中，使用流哈希为每个从套接字204发送至低层的分组添加标签，从而使这些低层识别哪个分组属于哪个流并向网络层提供反馈。分组在与流相关联的发送队列306内排队，并且如所提及的，SFB使用流哈希来增加和减少每个流保存在SFB容器1009 内的计数器(C₁、C₂)。SFB使用其存储器数据结构中的计数器来确定是否超出队列阈值。例如，如果流队列的分组数是阈值50，其保存该流的状态并发送反馈至传输层，打开针对支持该流的套接字204的流控制。因此，流从正常状态转入流控制状态，并在分组从队列出队并通过链路发送的同时保持该状态。

当队列中的分组数下降至低于阈值时，排队算法唤醒流建议器线程 1050，该流建议器线程唤醒并关闭针对套接字204的流控制。因此，套接字接下来可随意地通过低层向下传输分组，直到再次将其置于流控制状态。因此，图10A示出提供反馈，并无需要依靠诸如显式拥塞通知(ECN)的 TCP中的内部机制，允许相同的主机上的流在流控制/正常状态之间转换的机制。这减少了将只能被丢弃的数据向下发送至网络堆栈的不必要工作，从而改善了性能。此外，其允许减少驱动中的队列大小而不丢弃分组。这与应用盲目地将分组向下传输至栈而只能被驱动丢弃的旧机制不同。而在图10A中，因为网络堆栈由于队列监控知道什么在链路上传输，其可使用该信息智能地改变传输机制的行为。

在图10B中更详细地描述的一个实施例中，SFB算法获取分组的哈希值并计算针对SFB唯一的并被用来获取流的位的另一个哈希值。如图所示，套接字计算的初始哈希值是4位(01、02、03、04)，其可被提供给SFB 排队逻辑1060的哈希生成器1065。某些流哈希可具有值0，并被用来识别不使用此处描述的流控制机制的流。在一个实施例中，SFB生成随机数并使用随机数计算新哈希(A、B、C、D)。其使用这四个值填充两组容器：当前组和阴影组，每个具有两级，如图10B所示。该两级作为阵列被实现，使用新哈希值(在一个实施例中，每空位具有256位)对阵列进行索引。因此，使用流哈希值将流映射至SFB容器中。检查SFB容器以检查流是否存在。SFB算法的布隆过滤器功能性可检测SFB容器内是否不存在特定的流。如果存在一个，可对其进行索引以确定与该流相关联的数据(例如，上述概率和计数器)。只要流仍然存在，数据就由SFB维护。使用阴影组因为在一些时刻SFB重新哈希。由于布隆过滤器的特性，许多事物可映射于同一个容器。如果有许多套接字，一些发送太多数据的套接字可能影响其它映射于同一个容器的未发送很多数据的套接字。因此，SFB周期性地基于新随机数重新计算内部哈希。重新哈希后，容器可针对每个流移动。 SFB算法的其它细节可见于参考随机公平Blue：用于强制公平性的队列管理算法，其作为附录B附在本专利申请后并以引用的方式并入本文的。在该情况下，可使用阴影组将数据移入新容器。

应用驱动流量分类和流反馈，包括伺机行为、流控制、流挂起和传输层改善

上面参照图6-8进行描述的应用驱动流量分类可用来启用各种伺机行为。如所提及的，每个应用可明确地表示针对其套接字应使用哪种流量类。例如，一个应用使用诸如BK_SYS的低优先级流量类备份日期，但用户要进行语音通话。由于GSM的工作方式，如果在发送网络数据的同时进行语音通话，会增加语音通话劣化或掉线的概率。相似地，如果在语音通话时用户打开web浏览器，也会影响语音通话。为了减轻该现象，在一个实施例中，在用户进行语音通话时使用流量类来抑制不必要的流量。可在语音通话期间挂起任何不紧要的流量(例如，后台流量-BKS_SYS)。在一个实施例中，对于挂起的套接字，当出队发生时，系统假定没有要出列的分组，而当入队发生时，丢弃分组。因此，传输应用将其视为网络好像已停止那样，并可在再次尝试前等待。当通话相对较短时，其在通话结束后恢复(而不完全关闭套接字)。对BK_SYS外的流量类(例如，BK、BE等) 可使用这些技术。在一个实施例中，上述流控制/建议机制还可用来在这些情况下挂起套接字(例如，如果挂起，发送流控制指示)。因此，通过对某些套接字分类流量(例如，BK_SYS)，提供了处理流量挂起的智能反馈机制，并且在内核中启用对这些套接字的伺机行为。

注意挂起状态与流控制状态不同。在流控制状态，应用仍可发送数据，但是在挂起状态，阻塞链路(例如，由于语音通话时间过长)。因此，在挂起状态，停止发送更多的分组是有益的，因为只能将它们丢弃(因为队列挂起)。在一个实施例中，挂起的应用可选择启动计时器，并且如果挂起时间过长，就将连接关闭。

概括地说，在一个实施例中，当接收/发出语音通话时：

(1)系统的命令实体将蜂窝网络接口配置为伺机节流模式。

(2)在每个受影响的接口的分组调度器上配置伺机模式。

(3)调度器处理所有的要在该伺机模式下挂起的传输队列；当前，这只在BK_SYS传输队列实施。每个受影响的传输队列进入挂起模式；清除所有存在的分组，接下来的入队将导致丢弃。

(4)所有的伺机套接字(具有BK_SYS分类的套接字)将接收“挂起事件”。

在一个实施例中，当中断语音通话时：

(1)系统中的命令实体从蜂窝网络接口上移除伺机节流模式。

(2)每个受影响的接口的分组调度器退出伺机节流模式。

(3)调度器处理所有在该伺机模式中挂起的传输队列；当前，这只在 BK_SYS传输队列实施。恢复每个受影响的传输队列；容许接下来的入队。

(4)所有伺机套接字(具有BK_SYS分类的套接字)接收“恢复事件”。

此外，在接收方实现本文中称为“大接收负载”的性能优化。在一个实施例中，其通过调用网络堆栈中的函数来减少每分组代价的方法实现。例如，接收到10个分组，不处理所有10个分组，而可只处理1或2个分组。对于某些诸如AV类(流视频)的类型，可启用该优化。对于AV视频应用，软件将视频在开始放映前缓冲若干秒。因此，使用大接收负载技术，该应用可获得性能收益，因为它们对延迟不敏感。

在一个实施例中，因为栈上提供的反馈，可针对某些套接字调节TCP 发送和接收的方式。例如，如果应用将流分类为BK或BK_SYS，TCP将具有较小的主动性。例如，如果套接字是BK且在该链路上检测到高阻塞，应用可退避并为其它流接收更好的响应时间(例如，可延迟备份至网络的套接字以接收另一个套接字上的HTTP)。由于应用可明确地指定套接字流量类，所有这些都是可能的。

如上所述，在一个实施例中，对于可包括ARP、ACK响应、针对 IPV6的邻居发现、组播加入和离开、DCP相关分组、IPV6站路由器广告分组和DNS分组的网络控制分组使用最高的分类(CTL)。因此，如果用户使用低优先级套接字进行大的上载，不会延迟DNS操作。相似地，将不会由于低优先级套接字上的活动而延迟ACK响应。该类型的控制分组很小，并可发出而不引起任何延迟。

此外，如所提及的，在流控制和挂起状态期间上述技术和架构提供了内置TCP和UDP退避机制。通常TCP自身通过退避(例如，使用上述 ECN)响应拥塞。TCP发送分组，如果未接收到确认字符(ACK)，则反复发出分组并在每个重新传输时退避。如果知道分组仍在接口队列151-153 中并且只在链路可用后发送，则该重新传输是对资源的浪费。因此，在该情况下，无需使用内置TCP和UDP机制进行退避和重新传输。相反地，使用本文描述的技术，可发出流控制建议禁用重新传输功能。

此外，在一个实施例中，可对用于TCP的重新传输计时器进行微调来更有效的操作。通常，当未接收到ACK时，TCP后退重新传输计时器(例如，每次以2X增加)。因此，重新传输计时器可为若干秒。由于如上所述提供了从接口发出的反馈，该后退无需发生。每当获得流控制建议，我们可自动等待，因为我们知道分组在进行排队(并且无需要持续重新发送)。然而，在一个实施例中，可在针对套接字关闭流控制后使用重新传输计时器。

此外，始终将流建议传播至不向TCP写入任何更多数据的应用。因此，当流控制关闭时应用可丢弃全部的过期数据(例如，旧视频帧)并发送更新的数据。这特别对交互视频数据有益，在其中如果应用不丢弃过期数据，音频和视频可能会不同步。

对通过UDP传输的应用也可应用相似的原理。由于不具有本文中描述的流建议，UDP不会向其应用提供任何反馈。因此，如果接口丢弃，应用不会知道，还会继续传输因此必须在栈的较低级缓冲的分组，造成资源的浪费。相比之下，当在流控制状态下时，会立即丢弃应用的所有写入(从而节省缓冲资源)。上述操作显著地减少了由于缓冲分组造成的延迟。

用于处理入站网络流量、改善网络性能以及处理拒绝服务攻击的伺机轮询机制

如上所述，在一个实施例中，RXPOLL-capable接口在操作的输入轮询关闭模式和输入轮询打开(或传统)模式(例如， IFNET_MODEL_INPUT_POLL_OFF和IFNET_MODEL_INPUT_POLL_ON) 之间转换。在一个实施例中，使用输入轮询关闭模式作为默认/初始模式，并且网络堆栈在确定负载系数低时选择该模式。可通过评估变量P__平均、B_ _平均和W__平均(分别为分组的数量、字节和唤醒请求的值)来确定负载系数。参考图12中的DLL输入线程1203，在一个实施例中，当(P__平均≧P_hiwat &&(B__平均≧B_hiwat||W__平均≧W_hiwat))时，至输入轮询打开模式的切换完成，其中P_hiwat,B_hiwat和W_hiwat为P_hiwat,B_hiwat和W_hiwat为针对变量的低水印值。

相反地，当(P__平均≦P_lowat&&B__平均≦B_lowat&&W__平均≦ W_lowat)，至轮询关闭模式的切换完成，其中P_lowat,B_lowat和W_lowat 为针对所述变量的低水印值。

在一个实施例中，可基于某些工作负载任意地选择这些低水印值和高水印值，并应对其进行调整以适应将来的工作负载(以及变化的链路速度)。

基于高负载系数，以这种方式打开轮询，改善了性能并阻止拒绝服务攻击。这是因为，使用该轮询机制，在网络层的接收队列只在有足够的空间排队分组时，向在驱动层的队列请求分组。当不具有空间时(即，当驱动层队列已满时)，其将不会为请求更多的分组而轮询，接口会丢弃分组。因此，在驱动层防止了拒绝访问攻击，其不会向上传播至网络层。

不同API实施例

在一个实施例中实现的API是由软件组件(在下文中称为“API实现软件组件”)实现的接口，软件允许不同的软件组件(在下文中称为“API调用软件组件”)访问和使用由API实现软件组件提供的一个或多个函数、方法、流程、数据结构和/或其它服务。例如，API允许API调用软件组件的开发者(可以是第三方开发者)利用由API实现软件组件提供的指定特征。可以有一个或多于一个的API调用软件组件。API可以是计算机系统或程序库提供的源代码接口，以便支持来自软件应用程序的服务请求。

API可以编程语言的形式指定，在构建应用时可对其进行解释和编译，而不是对数据在存储器中如何排列进行明确的低级说明。API定义在访问和使用API实现软件组件的指定特征时API调用软件组件使用的语言和参数。例如，API调用软件组件通过API提供的一个或多个API调用(有时称为函数或方法调用)访问API实现软件组件的指定特征。API实现软件组件可响应于来自API调用软件组件的API调用通过API来返回值。尽管 API定义API调用的语法和结果(例如，如何引起API调用以及API调用做什么)，但API可以不揭示API调用如何实现由API调用指定的函数。通过调用软件(API调用软件组件)和API实现软件组件之间的一个或多个应用编程接口来传递各种函数调用或消息。函数调用或消息的传递可以包括发出、发起、引用、调用、接收、返回或响应函数调用或消息。因此， API调用软件组件可传递调用，并且API实现软件组件可传递调用。

以举例的方式，API实现软件组件2010和API调用软件组件可以是操作系统、库、设备驱动、API、应用程序、或其它软件模块(应当理解API 实现软件组件和API调用软件组件彼此间可以是相同或不同类型的软件模块)。API调用软件组件可以是经由网络通过API与API实现软件组件通信的本地软件组件(即在和API实现软件组件相同的数据处理系统上)或远程软件组件(即在和API实现软件组件不同的数据处理系统上)。应当理解API实现软件组件还可充当API调用软件组件(即，其可对其它API 实现软件组件提供的API进行API调用)，API调用软件组件也可通过实现提供给不同的API调用软件组件的API来充当API实现软件组件。

API可以允许以不同编程语言编写的多个API调用软件组件与API实现软件组件通信(从而API可以包括用于转换API实现软件组件和API调用软件组件之间调用和返回的特征)；然而，可以特定的编程语言实现 API。

图14示出包括实现API 1420的API实现软件组件1410(例如，操作系统、库、设备驱动、API、应用程序、或其它软件模块)的API架构的一个实施例。API 1420指定API调用软件组件1430可以使用的API实现软件组件的一个或多个函数、方法、类、对象、协议、数据结构、格式和/或其它特征。API 1420能够指定至少一个调用约定，该调用约定指定API实现软件组件中的函数如何从API调用软件组件接收参数以及函数如何向API 调用软件组件返回结果。API调用软件组件1430(例如，操作系统、库、设备驱动、API、应用程序、或其它软件模块)通过API 1420进行API调用，以访问并使用由API 1420指定的API实现软件组件1410的特征。API 实现软件组件1410可以响应于API调用通过API 1420向API调用部件 1430返回值。

应当理解，API实现软件组件1410可包括未通过API 1420指定的和对 API调用软件组件1430不可用的另外的函数、方法、类、数据结构、和/或其它特征。应当理解，API调用软件组件1430可在与API实现软件组件 1410相同的系统上或位于远程并通过网络使用API1420访问API实现软件组件1410。尽管图14示出与API 1420交互的单个API调用软件组件1430，应当理解，与API调用软件组件1430用不同的语言(或相同的语言)编写的其它的API调用软件组件可使用API 1420。

API实现软件组件1410、API 1420和API调用软件组件1430可以存储在机器可读介质中，其包括用于以机器(例如，计算机或其他数据处理系统)可读的形式存储信息的任何机制。例如，机器可读介质包括磁盘、光盘、随机存取存储器；只读存储器、闪存设备等。

在图15(“软件栈”)中，一个示例性实施例，应用可使用若干服务 API调用服务1或2，以及使用若干OS API调用操作系统(OS)。服务1 和2可使用若干OS API调用操作系统。

注意，服务2具有两个API，其中一个(服务2API 1)，从应用1接收调用并返回值，另一个(服务2API 2)从应用2接收调用并返回值。服务1(例如，可以是软件库)向OS API 1进行调用并接收返回的值，服务 2(例如，可以是软件库)向OS API 1和OS API 2两者进行调用并接收返回的值。应用2向OS API 2进行调用并接收返回的值。

示例性数据处理设备和接口

图16是图示了一种可在本发明的一些实施例中使用的一种示例性计算机系统的框图。应当理解，尽管图16图示了一种计算机系统的多个部件，但是并非旨在代表互连所述部件的任何特定架构或方式，因为这些细节与本发明关系不密切。应当理解，具有更少部件或更多部件的其他计算机系统也可以用于本发明。

如图16所示，数据处理系统形式的计算机系统2300包括与处理系统 2320、电源2325、存储器2330和非易失性存储器2340(例如，硬盘驱动器、闪存存储器、相变存储器(PCM)等)耦合的总线2350。如本领域公知的那样，总线2350可通过各种桥路、控制器、和/或适配器彼此连接。处理系统2320可从存储器2330和/或非易失性存储器2340获取指令，并且执行所述指令来执行如上所述的操作。总线2350将以上部件互连在一起，并且还把那些部件互连到可选的坞站2360、显示控制器和显示设备2370、输入/输出设备2380(例如，NIC(网络接口卡)、光标控件(例如，鼠标、触摸屏、触摸板等)、键盘等)、和可选的无线收发器2390(例如，蓝牙、 WiFi、红外等)。

图17是示出可在本发明的一些实施例中使用的一种示例性数据处理系统的框图。例如，数据处理系统2400可以是手持式计算机、个人数字助理 (PDA)、移动电话、便携式游戏系统、便携式媒体播放器、可包括移动电话、媒体播放器和/或游戏系统的平板式或手持式计算设备。作为另一实例，数据处理系统2400可以是网络计算机或另一设备内的嵌入式处理设备。

根据本发明的一个实施例，数据处理系统2400的示例性架构可用于上述的移动设备。数据处理系统2400包括处理系统2420，该处理系统可包括集成电路上的一个或多个微处理器和/或一个系统。处理系统2420与存储器 2410、电源2425(其包括一个或多个电池)、音频输入/输出2440、显示控制器和显示设备2460、可选的输入/输出2450、输入设备2470和无线收发器2430耦合。应当理解，图17中未示出的另外部件也可以是本发明的某些实施例中的数据处理系统2400的一部分，并且在本发明的某些实施例中可以使用比图16中所示更少的部件。另外，应当理解，如本领域公知的那样，可以使用图16中未示出的一个或多个总线来互连各种部件。

存储器2410可存储供数据处理系统2400执行的数据和/或程序。音频输入/输出2440可包括麦克风和/或扬声器，从而例如通过扬声器和麦克风来播放音乐和/或提供电话功能性。显示控制器和显示设备2460可包括图形用户界面(GUI)。可使用无线(例如，RF)收发器2430(例如，WiFi收发器、红外收发器、蓝牙收发器、无线蜂窝电话收发器等)来与其他数据处理系统通信。所述一个或多个输入设备2470允许用户向系统提供输入。这些输入设备可以是小键盘、键盘、触摸面板、多点触摸面板等。可选的其它输入/输出2450可以是用于坞站的连接器。

本发明的实施例可包括如上所述的各个步骤。这些步骤可以机器可执行指令的方式实现，该指令使得通用或专用处理器执行某些步骤。作为另外一种选择，这些步骤可通过包含用于执行所述步骤的硬连线逻辑的专用硬件部件、或者通过编程的计算机部件和定制硬件部件的任何组合来执行。

本发明的元素还可以被提供为用于存储机器可执行程序代码的机器可读介质。机器可读介质可包括但不限于：软盘、光盘、CD-ROM和磁光盘、 ROM、RAM、EPROM、EEPROM、磁卡或光卡、或适于存储电子程序代码的其他类型的介质/机器可读介质。

在前面的描述中，为了说明的目的，描述了许多具体细节以便提供对本发明透彻的理解。然而，对本领域的技术人员而言显而易见的是，可以在不存在这些具体细节中某些细节的情况下实践本发明。例如，对本领域的技术人员而言显而易见的是，本文所述的功能模块和方法可以实现为软件、硬件或它们的任何组合。此外，尽管本发明的实施例是在移动计算环境的背景下描述的(即，使用移动设备120-123；601-603)，但是本发明的基本原理不限于移动计算实现方式。实质上，任何类型的客户端或对等数据处理设备可用于一些实施例中，例如包括台式计算机或工作站计算机。因此，本发明的范围和精神应根据所附权利要求来判定。

Claims

1.一种具有网络层和驱动层的客户端设备，所述客户端设备包括：

在网络层配置的多个传输队列，其中所述多个传输队列中的一个或多个传输队列与多个分组服务类中的对应的分组服务类相关联；

分类器模块，被配置为至少部分地基于与分组相关联的分组类型将分组服务分类赋予分组；

队列管理器，被配置为至少部分地基于被赋予的分组服务分类和与所述一个或多个传输队列中的传输队列相关联的分组服务类的比较来将分组入队到该传输队列中，其中分组是网络控制分组，并且与包括网络控制分组的传输队列相关联的分组服务类对应于多个可用优先级中的最高优先级；以及

在所述网络层的分组调度器，被配置为至少部分地基于被赋予的分组服务分类来调度来自该传输队列的用于传输的分组。

2.根据权利要求1所述的客户端设备，其中，所述比较包括将分组类型与被赋予的分组服务分类相关联，并且其中所述队列管理器进一步配置为基于被赋予的分组服务分类选择传输队列。

3.根据权利要求1所述的客户端设备，其中，第一数量的分组服务类被映射到多个传输队列中的第二数量的传输队列，其中所述第一数量大于或者等于所述第二数量。

4.根据权利要求1所述的客户端设备，进一步包括：

应用，其中所述应用将对应的分组服务类与所述多个传输队列中的所述一个或多个传输队列相关联。

5.根据权利要求1所述的客户端设备，其中，所述驱动层被配置为响应于从网络层接收到通知而使分组从传输队列出队，其中所述通知至少部分地基于被调度的传输。

6.根据权利要求1所述的客户端设备，其中，与传输队列相关联的分组服务类基于以下中的至少一个：应用的分组延迟容忍水平，应用的分组损耗容忍水平，或者应用的流动弹性水平。

7.根据权利要求1所述的客户端设备，其中，与传输队列相关联的分组服务类对应于分组延迟容忍水平，并且分类器模块进一步配置为：

至少部分地基于第二分组的分组类型向第二分组赋予第二分组服务类，其中所述第二分组服务类对应于第二分组延迟容忍水平。

8.根据权利要求7所述的客户端设备，其中，分组延迟容忍水平对应于优先级，并且第二分组延迟容忍水平对应于第二优先级，其中第二优先级不同于该优先级。

9.根据权利要求1所述的客户端设备，其中，与传输队列相关联的分组服务类对应于流动弹性水平，并且分类器模块进一步配置为：

至少部分地基于第二分组的分组类型向第二分组赋予第二分组服务类，其中所述第二分组服务类对应于第二流动弹性容忍水平。

10.根据权利要求1所述的客户端设备，其中，与传输队列相关联的分组服务类包括以下中的至少一个：后台系统启动类；后台数据类；尽力服务类；响应式数据类；操作、执行和管理类；多媒体音频/视频流类；响应式多媒体音频/视频类；交互式视频类；交互式音频类；或网络控制类。

11.一种在具有网络层和驱动层的客户端设备上实现的用于传输网络分组的方法，所述方法包括：

在网络层配置多个传输队列，其中所述多个传输队列中的一个或多个传输队列与多个分组服务类中的对应的分组服务类相关联；

至少部分地基于与分组相关联的分组类型将分组服务分类赋予分组；

至少部分地基于被赋予的分组服务分类和与所述一个或多个传输队列中的传输队列相关联的分组服务类的比较，将分组入队到该传输队列中，其中分组是网络控制分组，并且与包括网络控制分组的传输队列相关联的分组服务类对应于多个可用优先级中的最高优先级；以及

至少部分地基于被赋予的分组服务分类来调度来自该传输队列的用于传输的分组。

12.根据权利要求11所述的方法，其中，所述比较包括将分组类型与被赋予的分组服务分类相关联，并且该方法进一步包括基于被赋予的分组服务分类选择传输队列。

13.根据权利要求11所述的方法，其中，第一数量的分组服务类被映射到多个传输队列中的第二数量的传输队列，其中所述第一数量大于或者等于所述第二数量。

14.根据权利要求11所述的方法，进一步包括：

通过在所述客户端设备上应用来将对应的分组服务类与所述多个传输队列中的所述一个或多个传输队列相关联。

15.根据权利要求11所述的方法，进一步包括通过所述驱动层响应于从网络层接收到通知而使分组从传输队列出队，其中所述通知至少部分地基于被调度的传输。

16.根据权利要求11所述的方法，其中，与传输队列相关联的分组服务类基于以下中的至少一个：应用的分组延迟容忍水平，应用的分组损耗容忍水平，或者应用的流动弹性水平。

17.根据权利要求11所述的方法，其中，与传输队列相关联的分组服务类对应于分组延迟容忍水平，并且所述方法进一步包括：

18.根据权利要求17所述的方法，其中，分组延迟容忍水平对应于优先级，并且第二分组延迟容忍水平对应于第二优先级，其中第二优先级不同于该优先级。

19.根据权利要求11所述的方法，其中，与传输队列相关联的分组服务类对应于流动弹性水平，并且所述方法进一步包括：

20.根据权利要求11所述的方法，其中，与传输队列相关联的分组服务类包括以下中的至少一个：后台系统启动类；后台数据类；尽力服务类；响应式数据类；操作、执行和管理类；多媒体音频/视频流类；响应式多媒体音频/视频类；交互式视频类；交互式音频类；或网络控制类。