用于带优先级的分组网的方法和路由选择器

摘要

本发明提出了一种在为数据分组进行路由选择时按优先级别安排分组的方法和设备。为各分组(F)规定一些优先级,而为每个优先级规定一个第一门限值(T1)和一个较高的第二门限值(T2)。结合每个分组,选择给定优先级的最老的分组(F),如果这个分组老于本优先级的第二门限值(T2),就舍弃所述分组(F),而选择下一个优先级。如果所述分组(F)老于本优先级的第一门限值(T1),就发送这个优先级的至少一个分组,直至这个优先级中最老的分组不老于本优先级的第一门限值(T1),再选择下一个优先级。

说明书

本发明与在为数据分组选择路由时按优先级别对分组排序的方法和设备有关。

图1示出了移动系统中本发明所涉及的一些部分。移动台MS通过无线接口Um与基站收发信台BTS通信。这些基站收发信台受属移动业务交换中心MSC管辖的基站控制器BSC控制。受一个基站控制器BSC控制的子系统，包括那些受这系统控制的基站收发信台BTS，称为基站子系统BSS。交换中心MSC与基站子系统BSS之间的接口称为A接口。移动系统的在A接口的MSC那侧的部分称为网络子系统NSS。基站控制器BSC与基站收发信台BTS之间的接口称为Abis接口。移动业务交换中心MSC连接入呼和出呼，执行与公众电话交换网PSTN的交换机类似的功能。此外，MSC还执行只属移动通信这类的功能，如在图1中未单独示出的网络用户寄存器配合下对用户位置的管理之类。

数字移动通信系统中所用的传统无线电连接是一种电路交换连接，也就是说分配给用户的连接资源在整个呼叫期间一直是保留着的。通用分组无线业务GPRS是一种为诸如GSM系统那样的数字移动通信系统设计的新业务。这种分组无线业务可参见ETSI规范TC-TR-GSM02．60和03．60。分组无线业务使得为移动台MS的用户提供有效利用无线电资源的分组型无线连接成为可能。对于分组交换连接，无线电资源只是在需发送语音或数据时才予保留。语音或数据集中在一些具有一定长度的分组内。在一个这样的分组通过无线接口Um发送后，如果发送方当时还没有新的分组需立即发送，那么这个无线电资源就释放给其他用户使用。

图1所示系统包括一个独立的GPRS服务提供节点，即SGSN15，用来控制网络侧分组数据业务的运作。这种控制包括，例如，将移动台接入和脱开系统，更新移动台位置，以及为数据分组发送到正确目的地编选路由。在本申请中，“数据”广义地表示任何在数字移动通信系统中传送的信息，例如编码成数字形式的语音、在计算机之间传送的数据、传真数据等。SGSN节点可以与基站收发信台BTS、基站控制器BSC或移动业务交换中心MSC结合，也可以是独立的。SGSN节点与基站控制器BSC之间的接口称为Gb接口。

诸如控制信令和语音或其他数据的信息在分组网内以GPRS·帧发送。每个帧F包括一个帧头1和一个数据部2。(此外，通过特别是无线接口发送的帧通常还有用来同步的不同比特模式，但帧的这种部分对于本发明来说是非本质的。)为了使系统可以知道是哪个移动台发送了这个帧，帧头1包括一个标识移动台的标识符，例如是暂时性逻辑链路标识符TLLI。当一个移动台在GPRS网内登记时，网就给这个移动台一个TLLI标识符，在GPRS连接期间使用。一旦GPRS连接建立以后，这个TLLI标识符就能重新指配给其他移动台使用。

在帧头1中，有时还能使用一个网络层服务接入点标识符NLSI和TLLI标识符，以指出移动台所用的应用协议。

在分组无线网中，可以想象这样一种情况：一个用户利用个人计算机PC通过分组网10、数据网11、路由器13和局域网LAN与另一个计算机14通信。一个长的数据传输或几个短的连续的数据传输在计算机PC和14之间例如用互联网FTP协议进行。同时，计算机PC的用户或其他用户发起一个交互式会话，例如用互联网Telnet协议。如果每个交互式会话的这些分组必需在连接的各节点上等待这个长时间的数据传输结束，那么在交互式会话中响应时间就会长得使这种业务不合实际要求。

网络运营者通常规定了几种不同的业务质量QoS，使得在较高业务质量情况下的传播延迟(可能还有分组丢失概率)小于较低业务质量情况。在本发明中，与业务质量关联的最重要参数是传播延迟。运营者可以规定例如三种业务质量，而为每种业务质量规定了两个传播延迟T_AVE和T₉₅，其中前者(T_AVE)为分组在运营者的网内的平均传播延迟，而后者(T₉₅)为所发送的分组中有95％的分组的延迟都不会超过的延迟。业务质量与传播延迟之间的对应关系可以如以下表1所示。

表1业务质量与传播延迟之间的典型对应关系业务质量　　T_AVE(ms)　　　　T₉₅(ms)　　　1　　　　　400　　　　　　600　　　2　　　　　500　　　　　　800　　　3　　　　　600　　　　　　1200

(显然，这些值只是作为例示而已。业务质量可以多于三种，算术平均可以用中值代替，95％也可以用其他百分比代替。)

网络运营者的问题是业务量在每天的各段时间内变化相当大，而且是随机的。业务量还呈现连续的，通常是显著的增大。用户一般要与运营者签定有关业务质量和与业务质量相应的最大延迟的要求的合同。当业务量增大时(偶然或永久性地)，用户所经受到的延迟就会超过按所述业务质量设定的最大值。这样，用户就会要求运营者必需部署更多的通信资源。随着用户数和业务量的增大，不断会出现这种情况。对于运营者来说，最好是尽量充分利用现有的传输容量，从而可以推迟新的投入，以便以后利用这些资金获得更新的技术。

本发明就是考虑到上述情况提出的。因此，本发明的目的是提供一种为分组进行路由选择的方法和设备，使得运营者的网络在运营者和用户之间的合同遵从表1所示时提供最佳的传输容量。

本发明的目的是采用特征如在各独立权利要求中所述的方法来达到的，而从属权利要求揭示了本发明的优选实施例。

本发明的基本思想是：如果某个分组的传播延迟已经超过最大传播延迟T₉₅，那么这个分组就能不再以运营者会对所述分组履行自己职责那种方式加以保存。这种情况发生在路由器中的业务量超过了路由器的传输容量的时候。如果运营者试图公平地对待所有用户，等同地延迟所有分组，这就很可能导致运营者对大多数用户都履行不了自己职责。情况可能会是例如只有总数的90％的分组能在时间少于延迟T₉₅内发送。于是，几乎所有用户都会感到运营者没有履行自己的职责。对于运营者(和大多数用户)来说，较可取的是将那些可用资源以可满足合同条件(即不超过传播延迟)方式分配给一系列用户和连接。在这种情况下，路由器首先将资源分配给那些仍然能在合同所规定的传播延迟内发送的分组。按照一个实施例，路由器甚至可以舍弃一个不再能在商定的传播延迟内发送的分组，从而使资源能更有效地分配给那些仍然能在商定的时间内发送的分组。舍弃的分组然后送至一个更高的协议层，使接收方请求发送方重发这些丢失的分组。

下面将结合附图参照各优选实施例对本发明进行更详细的说明。在这些附图中：

图1示出了一个移动通信系统中与本发明有关的各个部分；

图2为示出如何将各分组排入一个队列的方框图；以及

图3为例示本发明工作情况的流程图。

参见图1，分组网中的支持节点SGSN 15起着路由器的作用，将需通过基站系统BSC-BTS转发给移动台MS和与它连接的计算机PC的数据缓存入一个队列。由于无线接口Um形成一个明显的瓶颈，因此在SGSN节点15就形成一个队列。现在参见图2，在路由器15接收到分组F时，就确定了分组的优先级别。方框20例示了这种功能。一种简单的方式是可以根据在用户合同中规定的业务质量QoS直接确定优先级别。或者，用户也可以根据连接和／或应用确定优先级别。用户可以根据在帧F的帧头1中发送的TLLI标识符加以标识。TLLI标识符标识了移动台和SGSN节点之间的每个连接。应用可以TCP协议的端口编号清楚地加以标识。在图2中，分组处理例示成为每个优先级指定一个队列，作为例子在图2中示出了总共有7个的队列Q1-Q7。在本申请中，“队列”意味着任何可以获得与将各分组实际排入不同队列相同的效果的排列情况。就使用存储器而言，只保存一些与不同队列中的各分组有关的指针可能是比较经济的。一个队列例如能以链接表的形式实现，表中所列的每个元都含有一个指向下一个和／或上一个元的指针。此外，分组到达路由器的分组特定时间也存储在路由器内。

为每个优先级规定一个第一传播延迟门限值T1和一个比T1高的第二门限值T2。第一门限值T1与平均传播延迟T_AVE关联。类似，第二门限值T2与95％传播延迟T₉₅关联。然而，除了路由器，其他地方，特别是在无线电路径上，也要使分组延迟。但是，其他那些延迟通常基本上是不变的，因此可以从延迟T_AVE和T₉₅中减去以实验估计的这些不变部分。如果所估计的在路由器外的延迟为T₀，则T₁=T_AVE-T₀，T₂=T₉₅-T₀。

例如相应优先级的各分组的平均值，最好是移动平均，可以用作对分组传播延迟的一种估计。传播延迟的另一种估计例如是有关分组的实际延迟。

图3例示了一种实现本发明的开创性思想的可能方法。所谓“分组龄期”、“老分组”和“新分组”都是与分组F在路由器内已等待的时间有关。就各分组来看，在步骤30，选择某个优先级中最老的分组F。这例如可这样实现：为每个优先级指定各自的FIFO队列，如图2所示，将分组加到队列的尾端而从队列的始端取出。在步骤31，如果这个分组的龄期高于本优先级的第二门限值T2，就在下个步骤32舍弃所述分组F。在步骤33选择下个优先级。如果在步骤31这个分组的龄期不高于T2，就进至步骤34，将这个分组的龄期与本优先级的第一门限值T1进行比较。如果步骤34的比较结果是所述分组F的龄期高于本优先级的第一门限值T1，就在步骤35至少发送本优先级中的一个分组。分组相继发送直到这个分组中的最老的分组的龄期低于本优先级的第一门限值T1，然后再选择下一个优先级。

上述优先级别可以是与在用户合同中所规定的业务质量相同，也可以是在连接开始和／或期间根据具体连接要求商定。

业务质量可以在分组网上通过为每个分组配置一个指示业务质量的代码来通知路由器。由于在GPRS规范中规定了四种业务质量，因此用两个比特就可以加以标识。或者，也可以用一个独立的指示业务质量改变的消息来发出有关一个新的业务质量的信号。这个消息发送给一个位于连接的某处的路由器，这个路由器就会将改变了的业务质量存入它的存储器。

在每个分组都配有一个指示业务质量的代码时，连接上的每个节点都可以作出有关优先级别的判决。优先级别很容易用一个2比特的标识符加以改变，而不需要另外发送一个指示业务质量的消息。各个分组的优先级别很容易改变，而不用首先发送例如一个提高优先级别的消息，再在发送分组后发送一个降低优先级别的消息。

在改变业务质量时发送一个独立的指示这种改变的消息的情况下，就不必为每个分组设置一个指示业务质量的代码。这样做有另一个优点，计费比较简单，因为作为计费标准的业务质量的改变是用一个独立的消息通知的。

发给同一个移动台的各个分组通常没有在会话期间改变业务质量的机制，所以业务质量通常在用户登记需要利用GPRS连接时规定。

作为代替在步骤34逐个确定分组的龄期的步骤，可以是从所述优先级发送预定数量的分组，当然这数量不超过本优级中的分组数。图2中的参数K_i例示了从每个队列一次发出的数据量。与现有技术的用单个队列进行路由选择相比，如果采用多个队列Q_i而参数K_i不变，业务质量将得到改善。如果参数K_i例如根据业务质量加以调整，使得从高优先级队列一次发出的数据量大于从低优先级队列一次发出的数据量，那么业务质量可以得到进一步改善。队列Q₂例示了在这个队列中除了量K_i的数据外尚有少量数据的情况。这样，一次性地传输掉整个队列Q₂显然可改善有关应用的操作，但又不对其他用户和／或应用有多大损害。对于这种超过K_i的适当门限值例如为30至50％。相应，Q₄例示了一个队列只有少量数据的情况。如果在传输长队列前先传输掉这样的短队列，就可以缩短平均等待时间。

类似，作为代替在步骤31和32逐个确定需要舍弃的那些分组的龄期的步骤，可以是从所述优先级舍弃同一连接中的所有分组，因为较高的网络层的协议在任何情况下都是要重发这些分组的。

路由器通常用数字存储器和处理器实现。为了实现本发明所提出的方法及其各种变型只需改变路由器中处理器的软件即可。以上虽然是结合GPRS网中的节点举例对按照本发明为分组进行路由选择的情况作了说明，但对于熟悉本技术领域的人员来说显然清楚类似的路由器可用于任何其他通信系统。因此本发明及其实施方式并不局限于以上所举各例，所有按照本发明精神实现的种种变型都应属于本发明专利保护范围之内。