METHODS AND SYSTEMS FOR BANDWIDTH PROTECTION

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
10Forward
Citations 
0
Petitions 
1
Assignment
First Claim
1. A method for bandwidth estimation and correction in a communications network, the method comprising:
 calculating a round trip time (RTT) value and a packet loss rate (PLR) value for each packet of a set of packets transmitted at different points in time from a server to a client terminal over the communications network;
determining a bandwidth estimate based on the RTT and PLR values for the set of packets;
determining a bandwidth measurement based on the RTT and PLR values for the set of packets; and
determining a corrected bandwidth estimate based on the bandwidth estimate and the bandwidth measurement.
1 Assignment
0 Petitions
Accused Products
Abstract
Presented are methods and systems for providing bandwidth estimation and correction in a communications network. Bandwidth estimation and correction can include calculating a round trip time (RTT) value and a packet loss rate (PLR) value for each packet of a set of packets transmitted at different points in time from a server to a client terminal over the communications network; determining a bandwidth estimate based on the RTT and PLR values for the set of packets transmitted; determining a bandwidth measurement based on the RTT and PLR values for the set of packets; and determining a corrected bandwidth estimate based on the bandwidth estimate and the bandwidth measurement.
15 Citations
View as Search Results
PREDICTIVE THROUGHPUT MANAGEMENT  
Patent #
US 20100214923A1
Filed 02/20/2009

Current Assignee
Clearwire Ip Holdings LLC

Sponsoring Entity
Clearwire Ip Holdings LLC

COMMUNICATION SYSTEM, CALL CONTROL DEVICE, BASE STATION DEVICE AND RECORDING MEDIUM  
Patent #
US 20100135270A1
Filed 02/02/2010

Current Assignee
Fujitsu Limited

Sponsoring Entity
Fujitsu Limited

METHODS, SYSTEMS AND COMPUTER READABLE MEDIA FOR SUPPORTING A PLURALITY OF REALTIME TRANSPORT PROTOCOL (RTP) MULTIPLEXING ENABLEMENT METHODS IN A MEDIA GATEWAY  
Patent #
US 20120076131A1
Filed 12/01/2010

Current Assignee
Ribbon Communications Operating Company Inc.

Sponsoring Entity
Genband US LLC

Communication system, call control device, base station device and recording medium  
Patent #
US 8,295,870 B2
Filed 02/02/2010

Current Assignee
Fujitsu Limited

Sponsoring Entity
Fujitsu Limited

Predictive throughput management  
Patent #
US 8,644,154 B2
Filed 02/20/2009

Current Assignee
Clearwire Ip Holdings LLC

Sponsoring Entity
Clearwire Ip Holdings LLC

Methods, systems and computer readable media for supporting a plurality of realtime transport protocol (RTP) multiplexing enablement methods in a media gateway  
Patent #
US 8,971,311 B2
Filed 12/01/2010

Current Assignee
Ribbon Communications Operating Company Inc.

Sponsoring Entity
Genband US LLC

DATA TRANSMISSION METHOD AND APPARATUS  
Patent #
US 20170325129A1
Filed 07/24/2017

Current Assignee
Tencent Technology Company Limited

Sponsoring Entity
Tencent Technology Company Limited

METHOD AND APPARATUS FOR CONTROLLING SEND BUFFER OF TRANSMISSION CONTROL PROTOCOL IN COMMUNICATION SYSTEM  
Patent #
US 20180026899A1
Filed 07/21/2017

Current Assignee
The Board of Regents of the University of Colorado, Samsung Electronics Co. Ltd.

Sponsoring Entity
The Board of Regents of the University of Colorado, Samsung Electronics Co. Ltd.

Data transmission method and apparatus  
Patent #
US 10,462,707 B2
Filed 07/24/2017

Current Assignee
Tencent Technology Company Limited

Sponsoring Entity
Tencent Technology Company Limited

Method and apparatus for controlling send buffer of transmission control protocol in communication system  
Patent #
US 10,560,389 B2
Filed 07/21/2017

Current Assignee
The Board of Regents of the University of Colorado, Samsung Electronics Co. Ltd.

Sponsoring Entity
The Board of Regents of the University of Colorado, Samsung Electronics Co. Ltd.

INFORMATION PLANE FOR DETERMINING PERFORMANCE METRICS OF PATHS BETWEEN ARBITRARY ENDHOSTS ON THE INTERNET  
Patent #
US 20090122697A1
Filed 11/08/2007

Current Assignee
University Of Massachusetts

Sponsoring Entity
University Of Massachusetts

COMMUNICATION METHOD AND RECEIVING TERMINAL  
Patent #
US 20090285211A1
Filed 01/06/2006

Current Assignee
Panasonic Intellectual Property Corporation of America

Sponsoring Entity
Panasonic Corporation

BiLevel and FullColor Video Combination for Video Communication  
Patent #
US 20090284650A1
Filed 04/10/2008

Current Assignee
Microsoft Technology Licensing LLC

Sponsoring Entity
Microsoft Corporation

Resource Allocation in MultiStream IP Network for Optimized Quality of Service  
Patent #
US 20060156201A1
Filed 03/23/2006

Current Assignee
Microsoft Technology Licensing LLC

Sponsoring Entity
Microsoft Corporation

Method and system for measuring network performancefrom a server  
Patent #
US 20030046383A1
Filed 09/05/2001

Current Assignee
Microsoft Technology Licensing LLC

Sponsoring Entity
Microsoft Technology Licensing LLC

20 Claims
 1. A method for bandwidth estimation and correction in a communications network, the method comprising:
calculating a round trip time (RTT) value and a packet loss rate (PLR) value for each packet of a set of packets transmitted at different points in time from a server to a client terminal over the communications network; determining a bandwidth estimate based on the RTT and PLR values for the set of packets; determining a bandwidth measurement based on the RTT and PLR values for the set of packets; and determining a corrected bandwidth estimate based on the bandwidth estimate and the bandwidth measurement.  View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
 17. A system for bandwidth estimation and correction in a communications network, the system comprising:
a network analysis module configured to calculate a round trip time (RTT) and a packet loss rate (PLR) for each packet of a set of packets transmitted at different times from a server to a client terminal over the communications network; a bandwidth estimation module configured to determine a bandwidth estimate based on the RTT and PLR values for the set of packets; a bandwidth measurement module configured to determine a bandwidth measurement based on the values of RTT and PLR for the set of packets; and an estimationerror correction module configured to determine a corrected bandwidth estimate based on the bandwidth estimate and the bandwidth measurement.  View Dependent Claims (18, 19, 20)
1 Specification
This application claims the benefit of U.S. Provisional Application No. 61/017,898, filed Dec. 31, 2007, the contents of which is incorporated in its entirety herein by reference.
This invention relates to bandwidth prediction and, more specifically, to bandwidth estimation and prediction in a multimedia communications environment.
Current technology allows multimedia content to be communicated through various media such as airwaves, cable, and optic fiber and in various communication environments such as wired networks, thirdgeneration (3G) networks, WiFi networks, and the Internet. Various models have been established in order to estimate network parameters concerning performance and quality. Such network parameters may include, for example, available bandwidth in a network path, transmission latency, and data transmission rates. However, it may be difficult to determine these parameters because communication environments may be complicated and rapidly changing due to the timevarying nature of packet loss rate, network congestion, and client mobility.
One such model is used to estimate available bandwidth for a communications network. In this model, bandwidth may be determined by using a detection module at a client terminal that sends a request message (packet) to a server at a first point in time, T_{1}, and receives a response message (packet) from the server at a second point in time, T_{2}. Bandwidth is then calculated by the following equation (1):
BW=RP_{size}/(T_{2}−T_{1}), (1)
where BW is the bandwidth, and RP_{size }is the size of the response packet. However, network conditions, such as network congestion, may not be determined by the packet transmission time alone. Other variables, for example, packet loss rate and actual packet size received by a client, may need to be taken into account when calculating bandwidth. For example, in a relatively unstable wireless network, a RoundTripTime (RTT) of a packet may be subject to dramatic variation, which may result in an incorrect bandwidth calculation due to an extraordinary RTT, such as a burst RTT. Therefore, the model expressed in equation (1) may result in an erroneous estimate because it lacks a correction mechanism.
Another model uses “probing packets” to estimate unused capacity or available bandwidth. In this model, a onewaydelay (OWD) is calculated for each probing packet. An OWD trend (OWDT) is then calculated and used to determine whether the transmission rate of a probing packet is greater than the actual available bandwidth. The OWD and the OWDT can be determined by the following equations (2A) and (2B):
OWD=T_{a}−T_{s}+ClockOffset (2A)
OWDT=OWD_{i}−OWD_{i1}, (2B)
where T_{a }represents the time at which the probing packet arrives at a receiver, T_{s }represents the time at which a sender sends the probing packet, and ClockOffset represents the system clock offset between the sender and the receiver.
Because the OWDT is the difference between the OWD values of two consecutive packets, e.g., OWD_{i }of a packet i and OWD_{i1 }of a packet i−1, as indicated in equation (2B), the system clock offset may be eliminated after subtracting the OWD values. As a result, synchronization between the sender and the receiver may not be a matter of concern in this model. As the OWDT increases, the upper bound of the bandwidth estimate (measured as bytes per second (bps)) may decrease. On the other hand, as the OWDT decreases, the upper bound of the bandwidth estimate may increase. When the distance between the upper bound and the lower bound of the bandwidth estimate is smaller than a determined value, then, by using an approximation approach, convergence of the bandwidth estimate may be obtained. For example, the bandwidth estimate may be calculated as the average of the upper bound and the lower bound. However, the available bandwidth may be estimated incorrectly if the OWDT is not sufficient for the bandwidth estimate to reach convergence using an approximation approach. For example, the time measured may not be long enough or the number of packets detected may be insufficient.
Another model uses a filter to estimate available bandwidth. In this model, a Kalman filter may be employed to predict latency and available bandwidth in accordance with the RTT of probing packets using the following equations (3A) and (3B):
X_{k}^{e}=[L,1/BW]^{T} (3A)
X_{k}^{e}=φX_{k1}^{e}+K[z_{k}−HX_{k}^{e}], (3B)
where X_{k}^{e }is an estimate at a point in time k, L is latency, BWis bandwidth, T is a transpose operator for the matrix, φ is a state transition matrix [1,1], z_{k }is an RTT measurement, H is a measurement matrix, and K is a function of an estimate error covariance (“Q”) and a measurement error covariance (“R”). Q and R may be constants.
The Kalman filter accumulates a history of information, such as packet information or congestion information, and may generally reference the history when estimating bandwidth. However, when a session handoff occurs, network characteristics may change. The reference materials in the history, however, are not updated with the current network characteristics and may therefore cause erroneous estimates.
There is, therefore, a need to provide an improved way to estimate bandwidth in a multimedia communications environment
Consistent with embodiments of the present invention, systems and methods for bandwidth prediction are presented. A system for bandwidth estimation and correction in a communications network can include a network analysis module configured to calculate a round trip time (RTT) and a packet loss rate (PLR) for each packet of a set of packets transmitted at different times from a server to a client terminal over the communications network; a bandwidth estimation module configured to determine a bandwidth estimate based on the RTT and PLR values for the set of packets; a bandwidth measurement module configured to determine a bandwidth measurement based on the values of RTT and PLR for the set of packets; an estimationerror correction module configured to determine a corrected bandwidth estimate based on the bandwidth estimate and the bandwidth measurement; and a ratedecision module configured to determine a transmission rate based on the bandwidth estimate and an available buffer size of the client terminal, wherein the transmission rate is used by the server to adjust packet transmissions.
A method for providing bandwidth estimation and correction in a communications network consistent with embodiments of the present invention includes calculating a round trip time (RTT) value and a packet loss rate (PLR) value for each packet of a set of packets transmitted at different points in time from a server to a client terminal over the communications network; determining an bandwidth estimate based on the RTT and PLR values for the set of packets; determining a bandwidth measurement based on the RTT and PLR values for the set of packets; determining a corrected bandwidth estimate based on the bandwidth estimate and the bandwidth measurement; and determining a transmission rate based on the bandwidth estimate and an available buffer size of the client terminal, wherein the transmission rate is used by the server to adjust packet transmissions.
These and other embodiments of the present invention are further described below with reference to the following figures.
This description is explicative of certain embodiments of the invention and should not considered to be limiting. The system components and methods are represented herein by appropriate conventional symbols in the drawings, showing only those specific details that are pertinent to understanding the embodiments of the present invention, so as not to obscure the disclosure with details that will be readily apparent to those of ordinary skill in the art having the benefit of the description herein.
Communications system 100 may include a communications server 110 and a client terminal 130, wherein server 110 and client terminal 130 communicate with each other over a communications network 120. Client terminal 130 may, for example, include a personal computer (PC), a notebook computer, a personal digital assistant (PDA), or any electronic device capable of supporting network communication.
Communications network 120 may include: a wired network, a wireless area network (WAN), a thirdgeneration (3G) network, a WiMax network, or other suitable networks. Server 110 may be configured to transmit data packets to client terminal 130 over communications network 120 and thereafter receive a message, such as a realtime transmission control protocol (RTCP) reply, from client terminal 130.
Networkanalysis module 250 may be configured to transmit data packets to client terminal 130 and receive reply messages, such as RTCP reply messages, using communications network 120. An exemplary RTCP reply message may be a report message that contains information concerning client terminal 130 measurements, such as when data packets arrived, the number of packets received, and the buffer size used. In other words, the RTCP reply message may contain information relating to the channel condition of a given channel in communications network 120, over which a data packet is sent from server 110 to client terminal 130.
As shown in
RTT=T_{rc}−T_{tx} (4)
PLR=1−(N_{rc}/N_{tx}), (5)
where T_{rc }is the time at which a given reply packet was received by client terminal 130, T_{tx }is the time at which the corresponding data packet was transmitted by server 110, N_{rc }is the number of data packets (in bytes) received at client terminal 130 per unit of time, and N_{tx }is the number of the data packets (in bytes) transmitted by server 110 per unit of time.
The following example, using equations 4 and 5, illustrates sample RTT and PLR calculations. Given an initial transmission time of 00:00:00, May 16, 2007, wherein server 110 began transmitting a data packet to client terminal 130, and a receiving time of 00:00:01, May 16, 2007, wherein the response message from client terminal 130 was received by server 110, RTT is calculated as:
RTT=(2007.5.16,00:00:01)−(2007.5.16,00:00:00)=1 sec.
Further, given that a set of packets transmitted in sequence by server 110 is numbered 1, 2, 3, 4, and 5, and the packets received by client terminal 130 are numbered 1, 3, 4, and 5, the packet loss rate (PLR) is calculated as:
PLR=1−(4/5)=0.2.
As shown in
In one embodiment, bandwidth estimation module 210 may determine a bandwidth estimate using the following equation (6):
where BW(t) equals the bandwidth estimate (expressed as bps) at a point in time t, BW(t−1) is an a posteriori bandwidth estimate at a point in time t−1, and N is the size of a sliding timewindow.
The size of the sliding timewindow N may be adjusted by server 110 and, for example, could be set to approximately 30 seconds. However, N may be greater than 30 seconds, for instance, when there are handoffs exceeding a predetermined frequency or when there is network congestion exceeding a predefined value. An initial bandwidth estimate at a time t(0) for communications network 120 may depend on the type of network. For example, the initial bandwidth estimate for a 3G network, a LAN, and a wireless network may be approximately 384 Kbps, 3 Mbps and 1 Mbps, respectively. In equation (6), the a posteriori bandwidth estimate may refer to a bandwidth estimate made at a point in time (t−1) immediately previous to the time that the current bandwidth estimate is being made (t=0). The bandwidth estimate made at time (t−1) is the most up to date bandwidth estimate and may represent the network characteristics. However, a bandwidth estimate made at a prior point in time (t−2) in relation to the current time (t=0) may instead be used as the a posteriori bandwidth term if the channel condition in communications network 120 is stable. In that case, equation (6) may be rewritten as equation (6A):
Skilled persons in the art will now understand that equation (6) may be written in other forms if bandwidth estimates and RTT values obtained in prior estimates are useful in the current bandwidth estimation.
The bandwidth estimate, as seen from equation (6), may be a function of the size of the sliding timewindow N, and thus may result in an estimate error covariance Q. The calculations involving the RTT averages in equation (6) may be represented by a transition matrix φ, which may be regarded as a state transition of available bandwidth, i.e., a trend of available bandwidth, as equation (6B):
Since the state transition may be calculated based on averaging RTT values, the result of the state transition may be relatively smooth. For example, by using averaged RTT values, state transition divergence may be prevented due to network conditions, such as a burst RTT.
An estimate error covariance Q′ may be used to calculate an a priorierror covariance p^{−}(t), which may refer to an error covariance obtained prior to the current bandwidth estimate at time t. The a priorierror covariance may be expressed using the following equation (7):
p^{−}(t)=φ′^{2}p^{+}(t−1)+Q′, (7)
where p^{+}(t−1) is an a posteriori error covariance, which refers to an error covariance obtained a posteriori to the bandwidth estimate made at a time (t−1). In one embodiment, bandwidth estimation module 210 may include, but is not limited to, a Kalman filter to calculate the variable p^{−}(t).
As shown in
BW=(RP_{size}/RTT)×(1−PLR), (8)
where RP_{size }is the size of the data packets in bytes.
Packet loss may result from network conditions, such as congestion or poor connection quality in a wireless network, which may lead to a measurement error covariance R′. As shown in
K=p^{−}(t)/(p^{−}(t)+R′), (9)
where R′ is a measurement error covariance. The estimate error covariance Q′, in equation (7), the measurement error covariance R′, equation (9), are respectively defined in equations (10) and (11):
Q′=(BW_{e}−N_{rc})/N_{rc}, 0≦Q′≦1 (10)
R′=(BW_{m}−N_{rc})N_{rc}, 0≦R′≦1, (11)
where BW_{e }is a bandwidth estimate in bps, N_{rc }is the number of received data packets in bps, and BW_{m }is a bandwidth measurement in bps. A corrected bandwidth estimate BW_{c }may then be determined by equation (12):
BW_{c}=BW_{e}+(K×BW_{m}−BW_{e}) (12)
Thus, the expression “(K×BW_{m}−BW_{e})” in equation (12) represents the amount of correction for the bandwidth estimate. Generally, R′, being inversely proportional to K, may be smaller than Q′. Subsequently, an a posteriori error covariance p^{+}(t) may be determined by equation (13):
p^{+}(t)=p^{−}(t)[1−K] (13)
When a handoff of client terminal 130 occurs, network characteristics may change significantly. As a result, the RTT provided by network analysis module 250 may become unreliable. In one embodiment, when a handoff occurs, a first predetermined value, such as ‘1’, may be assigned to the estimate error covariance Q′ and a second predetermined value, such as ‘0’, may be assigned to the measurement error covariance R′. Also, if an RTCP response packet is lost, network analysis module 250 may fail to receive network characteristic information for a given period of time. In such a case, data needed for determining a bandwidth estimate may not be available. In one embodiment, consistent with the present invention, a third predetermined value, such as ‘0.8’, may be assigned to the estimate error covariance Q′ and a fourth predetermined value, such as ‘0.2’, may be assigned to the measurement error covariance R′ when the response packet is missing. In addition, when the bandwidth estimate (BW_{e}) equals the number of received packets (N_{rc}) in equation (10) and the bandwidth measurement (BW_{m}) equals the number of received packets (N_{rc}) in equation (11), then the variables Q, R′, and p^{−}(t) may be equal to zero, thus rendering the variable K in equation (12) insignificant. In such a case, as can be derived from equation (12), the corrected bandwidth estimate (BWc) equals the bandwidth estimate (BW_{e}).
Ratedecision module 240 may be configured to determine a transmission rate (TR), expressed in bps. As shown in
TR=min(BW_{e},B_{size}), (14)
where B_{size }is the buffer size for client terminal 130 determined by the following equation (14A):
B_{size}=max([C×B_{max}−B_{cur}],0), (14A)
where C is a constant, B_{max }is the maximum buffer size, and B_{cur }is the buffer size currently in use. The transmission rate (TR) may be used by server 110 to adjust packet transmissions.
The maximum buffer size may depend on the equipment at client terminal 130. For example, a desktop computer may have more available memory space to allocate as a buffer than a PDA. In one embodiment, the constant C may have a default value of approximately ‘0.8.’
A bandwidth estimate may be determined using equation (6) (302). The bandwidth estimate is based on the RTT for each packet transmitted at different time points within a sliding timewindow. A check may be made to determine whether a handoff or a handover occurred (303). If the check is true (303—Yes), then a first set of values for the estimate error covariance (Q′) and the measurement error covariance (R′) may be obtained (304). Otherwise (303—No), a check is made to determine whether a response message, such as an RTCP reply, has been lost (305). If the check is true (305—Yes), then a second set of values for Q′ and R′ may be calculated (306). Otherwise (305—No), Q′ may be calculated using equation (10) (307).
Next, an a priorierror covariance p^{−}(t) may be calculated using equation (7) (308). The a priorierror covariance is based on the value of the previously calculated estimate error covariance (Q′). A bandwidth measurement may be performed to provide a measure of available bandwidth using equation (8) (309). The bandwidth measurement is based on RTT and PLR values. If a value for the measurement error covariance (R′) was not previously calculated, then R′ is calculated (310) using equation (11) based on the bandwidth measurement (309).
Next, a check is made to determine whether the values of Q′, R′ and p (t) equal zero (311). If the check is true (311—Yes), then the bandwidth estimate (302) may serve as a corrected bandwidth estimate (312). That is, no bandwidth correction is needed, and the effective bandwidth correction value is reset, i.e., set to zero. Otherwise (311—No), a correction gain, such as a Kalman gain, may be calculated using equation (9) (313). The correction gain may be used to correct the bandwidth estimate (314) using equation (12). In some embodiments, the result of the correction, i.e., the corrected bandwidth estimate BW_{c}, may be provided to calculate the bandwidth estimate (302) for a subsequent packet using equation (6). The a posteriori error covariance p^{+}(t) may be calculated using equation (13) (315). The a posteriori error covariance is based on the calculated correction gain (313) and the calculated a priorierror covariance p^{−}(t) (308). The determined value of the a posteriori error covariance (315) may be used to calculate the priorierror covariance value for a subsequent packet (308).
A transmission rate may be determined using equation (14) (316), the transmission rate being based on the bandwidth estimate and the available buffer size at client terminal 130. Next, a check is made to determine whether bandwidth estimation and correction are to be performed for a next set of packets (317). If the check is true (317—Yes), then the above described method may be repeated for the next set of packets, and so on.
Other embodiments will be apparent to those skilled in the art from consideration of the specification and practice disclosed herein. It is intended that the specification and examples be considered as exemplary only, with a true scope and spirit of the invention being indicated by the following claims.