Source: http://www.google.com/patents/US7376141?dq=4168396
Timestamp: 2014-10-22 22:23:41
Document Index: 724130771

Matched Legal Cases: ['art,1', 'art,2', 'art,1', 'art,1', 'art,1', 'art,2']

Patent US7376141 - Method and system for encapsulating variable-size packets - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsEncapsulating packets includes receiving packets at a queue of an encapsulator. The following operations are repeated until certain criteria are satisfied. A number of packets are accumulated at the queue. A current encapsulation efficiency associated with the accumulated packets is determined. A next...http://www.google.com/patents/US7376141?utm_source=gb-gplus-sharePatent US7376141 - Method and system for encapsulating variable-size packetsAdvanced Patent SearchPublication numberUS7376141 B2Publication typeGrantApplication numberUS 10/322,120Publication dateMay 20, 2008Filing dateDec 17, 2002Priority dateDec 17, 2002Fee statusPaidAlso published asCA2508895A1, CN1748391A, CN1748391B, DE60314285D1, DE60314285T2, EP1573975A1, EP1573975B1, US20040117502, WO2004062203A1Publication number10322120, 322120, US 7376141 B2, US 7376141B2, US-B2-7376141, US7376141 B2, US7376141B2InventorsPhillip I. Rosengard, Marwan M. KrunzOriginal AssigneeRaytheon CompanyExport CitationBiBTeX, EndNote, RefManPatent Citations (15), Non-Patent Citations (4), Referenced by (2), Classifications (42), Legal Events (3) External Links: USPTO, USPTO Assignment, EspacenetMethod and system for encapsulating variable-size packetsUS 7376141 B2Abstract Encapsulating packets includes receiving packets at a queue of an encapsulator. The following operations are repeated until certain criteria are satisfied. A number of packets are accumulated at the queue. A current encapsulation efficiency associated with the accumulated packets is determined. A next encapsulation efficiency associated with the accumulated packets and a predicted next packet is determined. If the current encapsulation efficiency satisfies an encapsulation efficiency threshold and if the current encapsulation efficiency is greater than the next encapsulation efficiency, the accumulated packets are encapsulated. Otherwise, the packets continue to be accumulated at the queue.
13. A system for encapsulating packets for transmission in accordance with efficiency, comprising:
26. A method for encapsulating packets for transmission in accordance with efficiency, comprising:
30. A system for encapsulating packets for transmission in accordance with efficiency, comprising:
31. A method for encapsulating packets for transmission in accordance with efficiency, comprising:
forming a cell comprising at least a portion of the section. Description
TECHNICAL FIELD OF THE INVENTION This invention relates generally to the field of data communication and more specifically to a method and system for encapsulating variable-size packets.
BACKGROUND OF THE INVENTION Encapsulating packets in a communication system may involve the use of multiple queues for buffering packets waiting to be encapsulated. Packets at different queues, however, may experience different waiting times prior to encapsulation, also known as packet delay variation. Packet delay variation may introduce unwanted jitter into the communication system. Moreover, encapsulation according to known techniques may result in sub-optimal bandwidth usage of a communications channel. Furthermore, packets associated with Internet Protocol (IP) traffic may involve datagrams of variable size, which may affect encapsulation for optimal bandwidth usage. Consequently, encapsulating packets while controlling jitter and enhancing bandwidth utilization has posed challenges.
SUMMARY OF THE INVENTION In accordance with the present invention, disadvantages and problems associated with previous techniques for encapsulation of variable-size packets in data communication may be reduced or eliminated.
DETAILED DESCRIPTION OF THE DRAWINGS FIG. 1 illustrates a system 10 for encapsulating packets to form encapsulation sections. System 10 adjusts the size of the sections in order to achieve a high encapsulation efficiency while ensuring satisfaction of a jitter requirement. In general, encapsulating a large section increases jitter. However, encapsulating a small section, while reducing jitter, results in lower efficiency. System 10 predicts jitter and efficiency, and adjusts the size of the encapsulation sections to reduce jitter while maintaining efficiency.
System 10 may receive any suitable type of traffic, for example, moving pictures experts group-2 (MPEG-2) or MPEG-4 video traffic, voice over Internet protocol (VOIP), or Internet protocol (IP) packet traffic. The traffic may be classified according to jitter tolerance. According to one embodiment, traffic that is jitter tolerant comprises non-real-time traffic, and traffic that is not jitter tolerant comprises real-time traffic. Jitter tolerant traffic, however, may comprise any traffic that is jitter tolerant according to any suitable definition of �jitter tolerant,� and jitter intolerant traffic may comprise any traffic that is not jitter tolerant. For example, jitter intolerant traffic may include voice traffic.
System 10 includes real-time per-flow queues 40, non-real-time per-flow queues 30, and a processor 80. Real-time per-flow queues 40 buffer real-time traffic from real-time flows 15, and non-real-time per-flow queues 30 buffer non-real-time traffic from non-real-time flows 20. Each real-time per-flow queue 40 a may receive from real-time flows 15 a real-time flow 15a corresponding to the real-time per-flow queue 40 a. Similarly, each non-real-time per-flow queue 30 a receives a non-real-time flow 20 a associated with the non-real-time per-flow queue 30 a. As used in this document, �each� refers to each member of a set or each member of a subset of the set. Any number nv of real-time flows 15 may be used and any suitable number nd of non-real-time flows 20 may be used. Similarly, any suitable number of real-time per-flow queues 40 n v and non-real-time per-flow queues 30 n d may be used. According to one embodiment, queues that queue other types of traffic such as voice traffic or other real-time traffic may be used in place of or in addition to real-time per-flow queues 40 or non-real-time per-flow queues 30.
FIG. 3 illustrates an embodiment of a cell flow 300 resulting from the formation of cells 250 as described with reference to FIG. 2. In general, the cell flow 300 may include cells 250 ordered sequentially, consecutively, successively, serially, or in any similar manner therewith. According to one embodiment, each cell 250 may include, for example, IP cells or datagrams 240. In the illustrated example, a last portion of cell 250 c associated with datagram 240 c may be followed by a first portion of a cell 250 d associated with datagram 240 d. According to one embodiment, a cell 250 c may include additional capacity 280. Additional capacity 280 may result from the formation of cells as illustrated in FIG. 2. In the illustrated example, a cell flow 300 containing additional capacity 280 may contribute to a delay 350. Delay 350 or jitter experienced in a cell flow 300 may be calculated as the time lapsed between a last IP datagram 240 c and next IP datagram 240 d. Cell flow 300 may be formed in any other suitable manner, for example, with the exclusion of additional capacity 280 as described with reference to FIGS. 5 and 6.
Total number of real-time and non-real-time flows.
η(χ)
Encapsulation efficiency for a section with an χ-byte payload
Ti(j)
jth cell inter-arrival time in the ith flow
Size (in bytes) of the jth cell in the ith flow
μint er(i, j)
Exponentially weighted moving average of Ti(j)
μsize(i, j)
Exponentially weighted moving average of Si(j)
τi(j )
Ti(j) − μinter(i, j)
Si(j) − μsize(i, j)
Ti(m; r)
r-step forecast for the inter-arrival time of the ith flow, starting
Si(m; r)
r-step forecast for the cell size of the ith flow, starting
αi(m)
Coefficient of the autoregressive(1) model for the cell inter-
{circumflex over (α)}i(m)
Estimated value of αi(m)
βi(m)
Coefficient of the autoregressive(1) model for the cell size
{circumflex over (β)}i(m)
Estimated value of βi(m)
QRT pred(t)
Predicted number of QRT after t seconds
Ŝ(i) tot(x)
Predicted value of S(i) tot after x seconds
t(i) start(k)
Arrival time of the first bit of the kth cell in the ith flow
{circumflex over (t)}finish,2 (i) Predicted value of t(i) finish,2 W(i) {circumflex over (T)}next (i) + 8Ŝnext (i)/Ri tcurrent Current time at the encapsulator
In the illustrated method, packets are received at the per-flow queues 40 and 30 from real-time flows 15 and non-real-time flows 20. As an example, a packet of real-time flow 15 a is received by real-time per-flow queue 40 a. In describing the embodiment of FIG. 4, the term �per-flow queue� refers to a real-time per-flow queue 40 or a non-real-time per-flow queue 30.
η ⁡ ( χ ) = χ 204 ⁢ ⌈ ( χ + 24 ) 184 ⌉ , for ⁢ ⁢ 1 <= χ <= 4080 ( 1 ) where ┌.┐ is the ceiling function. Referring to Equation (1), the larger the value of the number χ of payload bytes, the higher the current encapsulation efficiency η(χ) However, the trend may not be monotonic due to padding of unused bytes in a cell. For example, the optimal efficiency ηopt, for one embodiment, is achieved when number χ=Sopt=4024 bytes, as described by Equation (2):
μinter(i,j+1)=ff interμinter(i,j)+(1−ff inter)T i(j+1) (3)μsize(i,j+1)=ff sizeμsize(i,j)+(1−ff size)S i(j+1) (4)
τi(k+1)=αi(k)τi(k)+σiε(k+1),k=1,2, (5) s i(k+1)=βi(k)s i(k)+ξiε(k+1),k=1,2, (6)
{circumflex over (T)} i(m;r)=({circumflex over (α)}i(m))r(T i(m)−μinter(i,m))+μinter(i,m) (7) Ŝ i(m;r)=({circumflex over (β)}i(m))r(S i(m)−μsize(i,m))+μsize(i,m) (8)
α ^ i ⁡ ( m ) = ∑ j = 1 m - 1 ⁢ T i ⁡ ( j ) ⁢ T i ⁡ ( j + 1 ) ∑ j = 1 m - 1 ⁢ T i 2 ⁡ ( j ) ( 9 ) β ^ i ⁡ ( m ) = ∑ j = 1 m - 1 ⁢ S i ⁡ ( j ) ⁢ S i ⁡ ( j + 1 ) ∑ j = 1 m - 1 ⁢ S i 2 ⁡ ( j ) ( 10 ) As previously described, the illustrated method may use a recursion procedure. According to one embodiment, the adjusted coefficient {circumflex over (α)}i(m) may be generated recursively each time a next packet arrival time needs to be predicted. To predict a next packet arrival time called for at step 408, a value for {circumflex over (α)}i(m) may be determined using recursive variables Yi(k) and Zi(k) as defined by Equations (11) and (12):
Y i ⁡ ( k ) ⁢ = def ⁢ ∑ j = 1 k ⁢ T i ⁡ ( j ) ⁢ T i ⁡ ( j + 1 ) = Y i ⁡ ( k - 1 ) + T i ⁡ ( k ) ⁢ T i ⁡ ( k + 1 ) ( 11 ) Z i ⁡ ( k ) ⁢ = def ⁢ ∑ j = 1 k ⁢ T i 2 ⁡ ( j ) = Z i ⁡ ( k - 1 ) + T i 2 ⁡ ( k ) ( 12 ) where the r-step prediction may be obtained using the following procedure once the mth measurement for the last arrival time is available:
{circumflex over (T)}i(1; r)=μinter(i,1)=Ti(1) Yi=0 Zi=0 (Recursion) For each subsequent cell arrival, m, do
Update EMWA: μinter(i,m)=ffinterμinter(i,m−1)+(1−ffinter)Ti(m) Yi=Yi+Ti(m−1)Ti(m) Zi=Zi+Ti 2(m−1) {circumflex over (α)}i(m)=Yi/Zi {circumflex over (T)}i(m;r)=({circumflex over (α)}i(m))r(Ti(m)−μinter(i,m))+μinter(i,m) End-recursion End-for The prediction of the next encapsulation efficiency at step 406 may be determined using a similar recursion procedure. Once the prediction of next encapsulation efficiency is determined, the method proceeds to step 410 to determine if the predicted next encapsulation efficiency exceeds the current encapsulation efficiency previously determined at step 404 by Equation (1). If the next encapsulation efficiency is lower than the current encapsulation efficiency, the method proceeds to step 416 to encapsulate the packets accumulated at the per-flow queue.
d i def = max ⁢ { 0 , ( t finish , 2 ( i ) - t finish , 1 ( i ) ) - ( t start , 2 ( i ) - t start , 1 ( i ) ) } ( 13 ) In the worst case, the computation of di may be performed after each packet arrives at the per-flow queue.
To initialize the process of determining delay di at step 412, t(i) start,1=t(i) finish,1=0 and t(i) start,2=t(i) start,1. Subsequently, when an encapsulation section is formed, the value of t(i) start,1 is updated and used to update t(i) finish,1 as described by Equation (14):
t finish , 1 ( i ) = t start , 1 ( i ) + 8 ⁢ S current ( i ) R i + Q RT + ⌈ S tot ( i ) - S current ( i ) + 20 184 ⌉ R encap ( 204 ) ⁢ ( 8 ) ( 14 ) where Stot (i) is the current number of bytes in the per-flow queue, Scurrent (i) is the size of the most recent packet to arrive from the ith per-flow queue, Ri is the peak rate in bits per second of the ith flow, Rencap is the rate of the encapsulator in bps, and QRT is the number of encapsulated cells in the real-time per-flow queue 40 at the time of computing t(i) finish,1. According to one embodiment, time t(i) finish,1 may be generated by, for example, using expression t(l) start,1+(8S(i) current/Ri), if it is computed at or after the last bit of the first packet arrives. After the encapsulation section including the first packet is formed, the value of time t(i) start,2 is updated.
Determining the delay di of Equation (13) at step 412 may require the prediction of time t(i) finish,2. The predicted value of time t(i) finish,2 may be referred to as {circumflex over (t)}(i) finish,2 and described by Equation (15):
t ^ finish , 2 ⁢ ( i ) ≈ t current + W ( i ) + Q RT pred ⁡ ( W ( i ) ) ⁢ ( 204 ) ⁢ ( 8 ) R encap ( 15 ) where:
W ( i ) ⁢ = def ⁢ T ^ next ( i ) + 8 ⁢ S ^ next ( i ) R i ( 16 ) and Qpred RT(t) is the predicted number of cells at the real-time buffer 50 after t seconds from the current time tcurrent(QRT pred(0)=QRT). The predicted packet arrival time {circumflex over (T)}next (i) and the predicted packet size Ŝ(i) next of Equation (16) may be obtained from Equations (7) and (8) as previously described.
To generate predicted time {circumflex over (t)}finish,2 (i) in accordance with Equation (15), the predicted number of cells at the real-time buffer 50 QRT pred(W(i)) may be obtained from Equation (17):
Q RT pred ⁡ ( W ( i ) ) ≈ max ⁢ { 0 , Q RT + ∑ j = 1 j ≠ i n v ⁢ ⌈ S ^ tot ( j ) ⁡ ( W ( i ) ) + 24 184 ⌉ - R encap ⁢ W ( i ) ( 204 ) ⁢ ( 8 ) } ( 17 ) where Ŝtot (j)(W(i)) is described as the number of additional bytes that could accumulate at queue j as defined by Equations (18) through (22):
j = ∑ k = 1 r * ⁢ S ^ j ⁡ ( m last ( j ) ; k ) ( 18 ) where the recursion variable r* is the largest integer that satisfies Equation (19):
∑ k = 1 r * ⁢ T ^ j ⁡ ( m last ( j ) ; k ) ≤ W ( i ) + t current - t start ( j ) ⁡ ( m last ( j ) ) ( 19 ) and where mlast (j) is the index of the most recent packet to arrive at the jth queue.
∑ k = 1 r ⁡ ( t ) ⁢ T ^ j ⁡ ( m last ( j ) ; k ) ≤ t ( 20 ) for any positive real value number t. Thus, using Equation (7) to obtain predicted time {circumflex over (T)}j(mlast (j);k) and manipulating the result into Equation (20), a recursion function r(t) may be obtained as described by Equation (21):
r ⁡ ( t ) ≤ t μ int ⁢ ⁢ er - ( T j - μ int ⁢ ⁢ er ⁡ ( j ) ) ⁢ ( α ^ j - ( α ^ j ) r ⁡ ( t ) + 1 ) μ int ⁢ ⁢ er ⁡ ( j ) ⁢ ( 1 - α ^ j ) ( 21 ) Finally, once the recursion function r(t) is generated from Equation (21), for example, by using an iterative process, recursion variable r* may be obtained by substituting time t in Equation (21) with W(i)+tcurrent−tstart (j)(mlast (j)) so that a solution for Ŝtot (j)(W(i)) may be obtained from Equation (22):
S ^ tot ( j ) = S tot ( j ) + ( S j - μ size ⁡ ( j ) ) ⁢ ( β ^ j - ( β ^ j ) r * + 1 ) 1 - β ^ j + r * ⁢ μ size ⁡ ( j ) ( 22 ) where {circumflex over (β)}j={circumflex over (β)}j(mlast (j)) and Sj=Sj(mlast (j)). Thus, using Equation (22) to obtain Ŝtot (j)(W(i)) for each j=1,2, . . . , nv, a value for the predicted number of cells at the real-time buffer 50 QRT pred(W(i)) may be obtained from Equation (17) and therefore a delay di in accordance with Equation (13) may be obtained.
FIG. 5 illustrates another embodiment of the formation of cells 550 from encapsulation sections 500. According to one embodiment, encapsulation section 500 may comprise a Multi-Protocol Encapsulation (MPE) section. Each encapsulation section 500 includes a section header 210, section data 215 and 218, and a section footer 214. Section header 210 may include, for example, digital video broadcasting (DVB) Multi-Protocol Encapsulation (MPE) header data. According to one embodiment, section header 210 may also include, for example, Digital Storage Media Command and Control (DSM-CC) header data. Encapsulation section 500 a comprises section data 218 and encapsulation section 500 b comprises section data 215, where each section data 218 and 215 comprises packets. According to one embodiment, each packet 218 and 215 may comprise an IP packet or datagram. Section footer 214 may include, for example, error correction codes. Datagram sizes may be variable, while section header 210 has, for example, 20 bytes, and section footer 214 has, for example, four bytes.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS5537408Jun 5, 1995Jul 16, 1996International Business Machines Corporationapparatus and method for segmentation and time synchronization of the transmission of multimedia dataUS5557608 *May 22, 1995Sep 17, 1996International Business Machines CorporationMethod and apparatus for transmission of high priority traffic on low speed communication linksUS6252855Dec 22, 1997Jun 26, 2001Cisco Technology, Inc.Method and apparatus for identifying a maximum frame size to maintain delay at or below an acceptable levelUS6483846Jul 10, 1998Nov 19, 2002Honeywell Inc.Middleware-based real-time communication systemUS6570849Oct 15, 1999May 27, 2003Tropic Networks Inc.TDM-quality voice over packetUS6701363 *Feb 29, 2000Mar 2, 2004International Business Machines CorporationMethod, computer program product, and system for deriving web transaction performance metricsUS6990105 *Sep 21, 1998Jan 24, 2006Nortel Networks LimitedTransporting multiprotocol datagramsUS7013318 *May 29, 2002Mar 14, 2006Raytheon CompanyMethod and system for encapsulating cellsUS7170897 *Dec 6, 2001Jan 30, 2007Alcatel Canada Inc.Method and apparatus for implementing point-to-multipoint communications over a connection- based data communication networkEP1178635A1Aug 4, 2000Feb 6, 2002Alcatel Alsthom Compagnie Generale D'electriciteMethod for real time data communicationEP1303083A1Jun 28, 2001Apr 16, 2003NEC CorporationPacket scheduling apparatusEP1317110A1Nov 30, 2001Jun 4, 2003Alcatel Alsthom Compagnie Generale D'electriciteIP platform for advanced multipoint access systemsWO1998047293A1Apr 8, 1998Oct 22, 1998Telia AbTransmission of mpeg-2 encoded video in atm networksWO2003103241A1May 12, 2003Dec 11, 2003Raytheon CoMethod and system for encapsulating cellsWO2004062203A1Oct 1, 2003Jul 22, 2004Raytheon CoMethod and system for encapsulating packets* Cited by examinerNon-Patent CitationsReference1Final Draft ETSI EN 301 192 V1.3.1 (Jan. 2003), European Standard (Telecommunications series), Digital Video Broadcasting (DVB); DVB specification for data broadcasting. (C) European Telecommunications Standards Institute 2003; (C) European Broadcasting Union 2003. All rights reserved. 58 pages.2J. K. Roussos, et al., "Congestion control protocols for interconnected LANs supporting voice and data traffic," Computer Communications, XP 000415044, vol. 17, No. 1, (C) 1994 Butterworth-Heinemann Ltd., pp. 25-34, Jan. 1994.3PCT, Notification of Transmittal of the International Search Report and the Written Opinion of the International Searching Authority, or the Declaration dated Dec. 22, 2004 for International Application No. PCT/US2004/026942, 12 pages.4PCT, Notification of Transmittal of The International Search Report or the Declaration, International Application No. PCT/US03/30957, 7 pages, Apr. 16, 2004.Referenced byCiting PatentFiling datePublication dateApplicantTitleUS7876785 *Dec 11, 2008Jan 25, 2011Alcatel LucentTransport of aggregated client packetsUS8385210 *Dec 18, 2008Feb 26, 2013Cisco Technology, Inc.System and method for detection and delay control in a network environment* Cited by examinerClassifications U.S. Classification370/412, 370/474, 370/471, 709/236, 370/473International ClassificationH04L12/46, H04L12/56, H04L12/28Cooperative ClassificationH04L2012/561, H04L47/10, H04L2012/5649, H04L47/6215, H04L12/4633, H04L49/9047, H04L12/5693, H04L47/621, H04L2012/5652, H04L47/36, H04L47/2441, H04L47/283, H04L2012/5651, H04L47/56, H04L12/5601, H04L47/2416, H04L49/90, H04L2012/5664, H04L2212/0025, H04L47/245European ClassificationH04L12/56K, H04L47/24B, H04L49/90, H04L47/62C, H04L47/28A, H04L47/24D, H04L47/10, H04L47/56, H04L49/90M, H04L47/62B, H04L47/24E, H04L47/36, H04L12/46E, H04L12/56ALegal EventsDateCodeEventDescriptionSep 19, 2011FPAYFee paymentYear of fee payment: 4Dec 30, 2008CCCertificate of correctionDec 17, 2002ASAssignmentOwner name: RAYTHEON COMPANY, MASSACHUSETTSFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:ROSENGARD, PHILLIP I.;KRUNZ, MARWAN M.;REEL/FRAME:013612/0594;SIGNING DATES FROM 20021126 TO 20021127RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google