Method and apparatus of precedence identification for real time services

BACKGROUND OF THE INVENTION

0001The present invention relates generally to quality of service in Internet Protocol (IP) networks, and more specifically to prioritizing data packets in an IP network.

0002Quality of service (QoS) in Internet Protocol (IP) networks is the throughput guarantee provided by an IP network to different data streams that are transported over the IP network (i.e., a guaranteed throughput level).

0003Network components, such as routers, often rely on indication mechanisms in an IP header of a packet to route the packet correctly. Several IP packet standards, or versions, exist. For example, packets can follow the standards defined by Internet Protocol version 4 (IPv4) (i.e., IPv4 packets) or Internet Protocol version 6 (IPv6) (i.e., IPv6 packets).

0004<figref idref="DRAWINGS">FIG. 1</figref> is a block diagram of an IPv4 packet header <b>100</b> including a Type of Service (TOS) field <b>104</b>. The TOS field <b>104</b> is for Internet service quality selection. The type of service is specified via parameters such as Precedence, Delay, Throughput, and Reliability. The IPv4 header <b>100</b> also includes a Time-To-Live (TTL) field <b>108</b>. The TTL field <b>108</b> contains a value that indicates to a network router or switch whether or not the packet has been in the network too long and is to be discarded. For a number of reasons, packets may not get delivered to their destination in a reasonable length of time. For example, incorrect routing tables may cause a packet to loop between two routers endlessly. A solution is to discard the packet after a certain time. The initial TTL value <b>108</b> is set in an 8 bit field of the packet header. Since each router is required to subtract at least one count from the TTL field, the count is usually used to indicate the number of router hops the packet is allowed before it must be discarded.

0005<figref idref="DRAWINGS">FIG. 2</figref> is a block diagram of an IPv6 header <b>200</b> including a Traffic Class (TC) field <b>204</b>. The IPv6 header <b>200</b> also includes a Hop Limit field <b>208</b>. The Hop Limit field <b>208</b> indicates the maximum number of hops that the packet can travel before being discarded. The Hop Limit field <b>208</b> is similar to the TTL value in an IPv4 packet.

0006<figref idref="DRAWINGS">FIG. 3(</figref><i>a</i>) provides more detail of the IPv4 TOS field <b>104</b>. The TOS field <b>104</b> includes a Precedence field <b>304</b> and a Priority field <b>306</b>. The Precedence field <b>304</b> is a field used to prioritize an IPv4 packet. The Precedence field <b>304</b> designates whether the network determines, using the Priority field <b>306</b>, the priority of a packet or whether the Priority field <b>306</b> is ignored and the network does not determine the priority of a packet. The Priority field <b>306</b> allows the network to take of advantage of various queuing and congestion control mechanisms that may exist within the network.

0007<figref idref="DRAWINGS">FIG. 3(</figref><i>b</i>) provides more detail of the IPv6 TC field <b>204</b>. The TC field <b>204</b> is available for use by originating routers and/or forwarding routers to identify and distinguish between different classes or priorities of IPv6 packets. The TC field <b>204</b> is used to provide various forms of “differentiated service” for IPv6 packets. Differentiated Service Code Points (DSCP), or DiffServe, is a marker in the header of each IP packet that prompts network routers to apply differentiated grades of service to various packet streams, forwarding them according to different Per-Hop Behaviors (PHBs). This enables Internet and other IP-based network service providers to offer differentiated levels of service to customers and their information streams. DiffServ has also been implemented in the TOS field of an IPv4 packet.

0008When a packet enters an IP router, its IP header is inspected. The inspection determines a next hop and a priority with which the packet is forwarded from the current router. The priority is determined by interpreting the Precedence field <b>304</b> and Priority field <b>306</b> for the TOS field <b>104</b> of an IPv4 packet and the Differentiated Service Code Points (DSCP) value in the TC field <b>204</b> of an IPv6 packet. If a packet's header fields do not provide enough guidance to determine its priority, a deep packet inspection is performed to gain more information from which a priority decision can be made.

0009A packet's priority affects when the packet is scheduled to be transmitted to its next hop. In wired networks, the task of packet scheduling is to associate a packet with a time slot (at a constant power, data rate, and through one shared channel). In wireless networks, packet scheduling can be more general than that—its function is to schedule such resources as time slots, powers, data rates, channels, or a combination of them, when packets are transmitted. Specifically, based on a source's characteristics, QoS requirements, channel states, and/or queue lengths, a wireless scheduler assigns time slots, powers, data rates, and/or channels to the packets for transmission.

0010Real-time Transport Protocol (RTP) is an Internet protocol for transmitting real-time data such as audio and video. RTP supports streaming data. To schedule an RTP voice stream over a wireless channel, the time that the packet is due at a destination router (i.e., the packet's deadline) needs to be known by the router sending the voice stream. Packets of an RTP voice stream, however, may be encrypted. If the voice stream is encrypted, then the deadline cannot be retrieved from the packet. Specifically, if a packet is encrypted, then any method that involves packet inspection will typically not be effective because no additional knowledge of the importance of the packet data can be obtained due to the encryption.

0011Wireless links are typically either the first or last link in the network. The majority of QoS is often determined by behavior of the last wireless hop node (e.g., router). The last wireless hop node will not typically be able to use a packet's header alone to determine the relative importance of a packet among packets of the same service ensemble (e.g., packets associated with a single Voice over Internet Protocol (VoIP) telephone call).

0012Therefore, there remains a need for an improved way of identifying the priority of a packet at the last hop node.

BRIEF SUMMARY OF THE INVENTION

0013The present invention is a method and apparatus for transmitting a data packet from a source to a destination via a network path having a number of hops. The sum of a playback delay associated with the data packet and the number of hops are stored in a header of the data packet. The data packet is transmitted from the source to the destination via the network path.

0014In one embodiment, the sum of the playback delay and the number of hops is calculated at the source. Alternatively, the sum may be calculated at the destination.

0015In one embodiment, the data packet is processed (e.g., played by a wireless telephone) during a VoIP telephone call before the sum of the playback delay and the number of hops expires. The sum of the playback delay and the number of hops may be stored in the TTL field of the header of the packet. The number of hops can be determined by, for instance, the source pinging the destination. The priority of the data packet can be determined from the playback delay and the number of hops.

0016These and other advantages of the invention will be apparent to those of ordinary skill in the art by reference to the following detailed description and the accompanying drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

0017<figref idref="DRAWINGS">FIG. 1</figref> is a block diagram of a prior art IPv4 packet header;

0018<figref idref="DRAWINGS">FIG. 2</figref> is a block diagram of a prior art IPv6 packet header;

0019<figref idref="DRAWINGS">FIG. 3(</figref><i>a</i>) is a block diagram of a prior art Type of Service (TOS) field of an IPv4 header of a packet;

0020<figref idref="DRAWINGS">FIG. 3(</figref><i>b</i>) is a block diagram of a prior art Traffic Class (TC) field of an IPv6 header of a packet;

0021<figref idref="DRAWINGS">FIG. 4</figref> is a block diagram of a transmitting router communicating a packet to a destination router in accordance with an embodiment of the present invention;

0022<figref idref="DRAWINGS">FIG. 5</figref> is a flowchart of the steps performed to schedule the deadline of a packet in accordance with an embodiment of the present invention;

0023<figref idref="DRAWINGS">FIG. 6</figref> is a flowchart of the steps performed by the destination router to determine the priority of a packet received from the transmitting router in accordance with an embodiment of the present invention; and

0024<figref idref="DRAWINGS">FIG. 7</figref> is a high level block diagram of a computer in accordance with an embodiment of the invention.

DETAILED DESCRIPTION

0025In accordance with an embodiment of the present invention, <figref idref="DRAWINGS">FIG. 4</figref> shows a block diagram of communications sent from a sending node <b>404</b> to a receiving node <b>406</b>. In one embodiment, the sending node <b>404</b> and/or the receiving node <b>406</b> are wireless telephones. The sending node <b>404</b> transmits packets to a transmitting router <b>408</b> (e.g., a base station router (BSR)). The transmitting router <b>408</b> can set the TOS or TC field of a packet to be Diff Serv compliant.

0026The transmitting router <b>408</b> then sets the TTL value to a predetermined maximum (i.e., TTL_MAX). This predetermined maximum can be a parameter negotiated between the transmitting router <b>408</b> and a destination router <b>424</b> (e.g., a BSR) (TTL_NEG) (e.g., in a Session Initiation Protocol (SIP)/Session Description Protocol (SDP) session negotiation). Alternatively, the predetermined maximum can be a default maximum.

0027The packet is then transmitted to a second hop <b>412</b>, a third hop <b>416</b>, and a fourth hop <b>420</b>. Each of these hops <b>412</b>, <b>416</b>, <b>420</b> can be, for example, routers or switches. Each router <b>412</b>, <b>416</b>, <b>420</b> subtracts one from the TTL field of the packet's header. The packet is then sent to the destination router <b>424</b>. The destination router <b>424</b> extracts the received TTL (i.e., TTL_RX). In one embodiment, the destination router <b>424</b> then determines the hop count. The hop count is determined from the formula: <br />Hops=<i>TTL</i>_MAX<i>−TTL</i>_RX<br /> or the formula: <br />Hops=<i>TTL</i>_NEG<i>−TTL</i>_RX

0028The destination router <b>424</b> includes a scheduler <b>428</b>. The scheduler <b>428</b> guarantees that a packet arrives at the receiving node <b>406</b> before its hop count is exhausted. The scheduler <b>428</b> uses the hop count to determine how much flexibility it has in scheduling the packet. Every packet time (i.e., a predetermined time interval associated with a packet), the scheduler <b>428</b> subtracts 1 from the hop count.

0029The destination router <b>424</b> then sets the TTL value for subsequent real-time (RT) packets to TTL=Hops+1. The destination router <b>424</b> then performs a continuous check on TTL_RX. If TTL_RX≠0, then the destination router <b>424</b> reevaluates the hop count and recalculates the number of hops, if necessary. If TTL_RX=0, the destination router <b>424</b> continues to use TTL=Hops+1.

0030Although described above as using the TTL field, the invention also applies to IPv6 packets and, in particular, to using the Hop Limit field. As described in more detail below, an embodiment of the present invention uses the TOS or TC fields in conjunction with the TTL or Hop Limit fields.

0031<figref idref="DRAWINGS">FIG. 5</figref> shows a flowchart illustrating the steps performed in accordance with an embodiment of the invention to determine the deadline of a voice stream packet. Deep packet inspection is not needed to determine the deadline of a packet because of the use of the modified TTL (or Hop Limit) field.

0032First, the number of hops required for the voice packets to travel from the transmitting router <b>408</b> to the destination router <b>424</b> over an IP network is determined in step <b>504</b>. In one embodiment, the transmitting router <b>408</b> pings the destination router <b>424</b> to determine the number of hops. The reason for determining the number of hops is because the destination router <b>424</b> then uses the IP router hop count between the transmitting router <b>408</b> and the destination router <b>424</b> to determine the deadline of the packet.

0033Next, the time period needed to process the packet (e.g., output on a wireless telephone) is determined by the destination router <b>424</b>. A typical VoIP application buffers incoming packets in a playout buffer and delays their playout in order to compensate for variable network delays (i.e., jitter). This allows the slowest packets to arrive in time to be played out. The length of a playback delay (i.e., the length of the playout buffer) imposed by the destination router <b>424</b> is determined in step <b>508</b>.

0034The reason for determining the playout buffer length in the destination router <b>424</b> is to enable the determination of how many extra “virtual” hops need to be added to the hop count to indicate the deadline of the packet. Determining a “virtual” hop is adding an amount to the TTL field for the playout buffer that is equivalent to the amount added to the TTL field for a hop.

0035For example, if the hop count between the transmitting router and the destination router is N hops, and the playout buffer in the destination router is X packets, then the hop count needs to be set to N+X. Thus, X represents the relative importance of the packet compared with other packets.

0036The hop count remaining when the packet is received by the destination router is then used as an indicator to the scheduler of the deadline of a packet in step <b>512</b>. When the voice packet travels over the IP network from the transmitting router to the destination router, every IP router subtracts one from the hop count set by the transmitting router.

0037The destination router receives a hop count of X. As described above, the destination router then uses this remaining hop count X as an indicator to the wireless channel scheduler of how much flexibility the scheduler has in scheduling the packet. Every packet time, the wireless channel scheduler subtracts 1 from X. If X is large, the wireless channel scheduler can use more aggressive scheduling mechanisms for delivering the packet at the terminal compared to small values of X. X represents the relative importance of the packet because, as X increases, the scheduler has more time before the packet has to be used. Similarly, as X decreases, the scheduler has less time before the packet has to be used. As a result, X represents the importance of the packet (i.e., the more important a packet is, the lower X is).

0038For a packet transmitted by the receiving node <b>406</b> to the sending node <b>404</b>, the same process applies. Thus, when the destination router <b>424</b> receives a packet from the receiving node <b>406</b> for transmission to the sending node <b>404</b>, the destination router <b>424</b> already “knows” what to set the packet's hop count to based on the packet(s) that the destination router <b>424</b> previously received from the transmitting router <b>408</b>. Once this hop count is set, the transmitting router <b>408</b> receives the packet and can determine, in step <b>512</b>, that the packet has, for example, a high priority and needs to be delivered to the sending node <b>404</b> quickly.

0039<figref idref="DRAWINGS">FIG. 6</figref> shows a flowchart of the steps performed by the destination router <b>424</b> upon receipt of a packet. The destination router <b>424</b> receives inbound packets from the IP network in step <b>604</b> and checks the TOS (or TC) field and the TTL (or Hop Limit) field in step <b>608</b>. The destination router <b>524</b> then determines whether the TOS (or TC) field equals “immediate” or “priority” in step <b>612</b>. If the TOS field does not equal “immediate” or “priority” in step <b>612</b>, then the destination router <b>424</b> (i.e., the scheduler <b>428</b>) uses “normal” priority handling methods in step <b>614</b>. Normal priority handling methods include having the packet traverse along a destination router's queue in the order of which the packet went onto the queue (e.g., when the TTL field is high enough such that the TTL field does not decrease down to zero before being sent out of the destination router <b>424</b>).

0040If the TOS field=“immediate” or “priority” in step <b>612</b>, then the destination router <b>424</b> determines whether TTL=0 in step <b>616</b>. If so, then the destination router <b>424</b> (i.e., the scheduler <b>428</b>) prioritizes the packet for transmission (i.e., expedites the packet) in step <b>620</b>. The destination router <b>424</b> expedites the packet by moving the packet up in the destination router's queue in order to “play” the packet as soon as possible. If not, then the destination router <b>424</b> uses normal prioritized transmission for the packet in step <b>624</b>. The destination router <b>424</b> may also receive packets from the receiving node <b>406</b>. When this occurs, the destination router <b>424</b> decrements the TTL field by one (i.e., normal TTL handling behavior).

0041The prior description describes embodiments of the present invention in terms of the processing steps required to implement an embodiment of the invention. These steps may be performed by an appropriately programmed computer, the configuration of which is well known in the art. An appropriate computer may be implemented, for example, using well known computer processors, memory units, storage devices, computer software, and other components. A high level block diagram of such a computer is shown in <figref idref="DRAWINGS">FIG. 7</figref>. Computer <b>702</b> contains a processor <b>704</b> which controls the overall operation of computer <b>702</b> by executing computer program instructions which define such operation. The computer program instructions may be stored in a storage device <b>712</b> (e.g., magnetic disk) and loaded into memory <b>710</b> when execution of the computer program instructions is desired. Computer <b>702</b> also includes one or more interfaces <b>706</b> for communicating with other devices (e.g., locally or via a network). Computer <b>702</b> also includes input/output <b>708</b> which represents devices which allow for user interaction with the computer <b>702</b> (e.g., display, keyboard, mouse, speakers, buttons, etc.). One skilled in the art will recognize that an implementation of an actual computer will contain other components as well, and that <figref idref="DRAWINGS">FIG. 7</figref> is a high level representation of some of the components of such a computer for illustrative purposes. For example, computer <b>702</b> may represent the transmitting router and/or the receiving router of <figref idref="DRAWINGS">FIG. 4</figref>. In addition, one skilled in the art will recognize that the processing steps described herein may also be implemented using dedicated hardware, the circuitry of which is configured specifically for implementing such processing steps. Alternatively, the processing steps may be implemented using various combinations of hardware and software. Also, the processing steps may take place in a computer or may be part of a larger machine.

0042The foregoing Detailed Description is to be understood as being in every respect illustrative and exemplary, but not restrictive, and the scope of the invention disclosed herein is not to be determined from the Detailed Description, but rather from the claims as interpreted according to the full breadth permitted by the patent laws. It is to be understood that the embodiments shown and described herein are only illustrative of the principles of the present invention and that various modifications may be implemented by those skilled in the art without departing from the scope and spirit of the invention. Those skilled in the art could implement various other feature combinations without departing from the scope and spirit of the invention.