TWI496457B - Hierarchical available bandwitdh estimation method for video system - Google Patents

Description

Hierarchical available bandwidth estimation method for video system

The present invention relates to a bandwidth estimation method, and more particularly to a hierarchical available bandwidth estimation method, and is applicable to a video system such as Internet Protocol Television (IPTV).

With the rapid development of multimedia networks, the Open IPTV Forum (OIPF) of international organizations is working to promote the standardization of IPTV. It can be seen that IPTV has become the main development trend of multimedia networks. IPTV is Internet Protocol Television (IPTV), which is a broadband TV (Broadband TV). IPTV is a system for transmitting television information using a broadband network as a medium, which can deliver digital television services to subscribers through broadcast protocols over broadband. Because of the need to use the Internet, IPTV service providers often provide related services such as connecting to the Internet and IP phones, which can also be called "Triple Play". IPTV is a digital TV that is played in digital mode. Therefore, ordinary TV sets need to match the corresponding set-top box receiving channels. Therefore, suppliers usually provide on-demand video services to customers.

In the Internet, bandwidth is a measure of the ability of a network to transmit information. It is measured by the bit rate. Due to the improvement of transmission media and the advancement of transmission technology, the transmission rate of broadband networks is getting faster and faster, which also promotes the development of multimedia coding technology, which makes the sound quality and picture quality of multimedia audio and video content better and better. High-definition multimedia audio and video content greatly enhances the amount of data transmitted over the network. Therefore, when these multimedia content is transmitted over the network, the network bandwidth becomes an important indicator of quality of service.

Because the Internet has a distributed (Distributive), Uncooperative, Heterogeneous architecture, and there are many uncertain factors, such as network traffic with time-variant or burst characteristics. And the terminal-to-terminal routing is asymmetric (Asymmetrical), and the Internet service is different depending on the Service Level Agreements signed by the end user and the Internet Service Provider (ISP). The network bandwidth that the Internet Server Provider (ISP) can provide to the end users is different, which often results in different network bandwidth capabilities of each end user. In such a heterogeneous network, due to the end user requirements of different bandwidth capabilities, only the traditional image compression technology supporting a fixed bit rate, it is necessary to suppress multimedia content suitable for various bit rates, which is bound to cause content providers. In addition to the additional burden and cost considerations, various video coding has been developed to solve this problem, so that multimedia images are more suitable for transmission in heterogeneous networks (Heterogeneous Networks) with different bandwidths. In order to enable video coding to operate effectively, the multimedia service server must know the information of the bandwidth capability of the terminal user, so as to provide multimedia audio and video content with appropriate bit coding rate for terminal users of different bandwidth capabilities, so the end user Estimation of the available bandwidth becomes quite important for the multimedia service server.

An object of the present invention is to provide a hierarchical available bandwidth estimation method, which uses a detection packet sequence including a complex detection rate to effectively reduce the bandwidth estimation time; each detection rate uses multiple packets. The accumulation of the unidirectional path delay is more obvious, so that the position of the turning point can be easily confirmed; and the hierarchical detecting method is used to estimate the bandwidth capability of the end user to accurately measure the bandwidth range of the end user.

To achieve the above object, a preferred hierarchical available bandwidth estimation method of the present invention is for a video system, the video system comprising a transmitting device and a receiving device, the hierarchical available bandwidth estimation method comprising the following steps:

(a) the transmitting device selects a first detection bandwidth range between a first upper bandwidth threshold and a first lower threshold bandwidth, and the first detection bandwidth is determined by a complex frequency Wide composition.

(b) the transmitting device initializes a probe packet sequence according to the upper bandwidth threshold and the lower bandwidth threshold of the first detection bandwidth, the probe packet sequence comprising a plurality of packet groups, each of the The packet groups correspond to each of the bandwidths, each of the packet groups corresponds to a detection rate, and each of the packet groups is composed of a plurality of detection packets.

(c) The transmitting device transmits the probe packet sequence to the receiving device via the network.

(d) The receiving device calculates a one-way delay of each of the detection packets according to the transmission time of the detection packets from the transmission device and the reception time to the receiving device.

(e) determining a delayed cumulative turning point according to the one-way path delay of each of the detecting packets, and generating a second detecting bandwidth range formed in the first detecting bandwidth range, wherein the second detecting The bandwidth range is smaller than the first detection bandwidth range, and the second detection bandwidth range includes a second upper bandwidth threshold and a second lower threshold bandwidth.

(f) comparing the second detection bandwidth range with a predetermined bandwidth, and when the second detection bandwidth range is less than a predetermined bandwidth, calculating in the bandwidths of the second detection bandwidth To form an available bandwidth; when the second detection bandwidth is greater than the predetermined bandwidth, step (g) is performed.

(g) reinitializing the probe packet sequence according to the second probe bandwidth range, and continuing to perform step (c) until the available bandwidth is formed.

The present invention discloses a hierarchical available bandwidth estimation method, which can effectively reduce the bandwidth estimation time and make the accumulation of the unidirectional path delay more obvious, so that it is easy to confirm the turning point position; The detection method is used to estimate the bandwidth capability of the end user to accurately measure the bandwidth range of the end user.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS The present invention will be described in detail with reference to the accompanying drawings

1 is a block diagram of a system for performing a hierarchical available bandwidth estimation method in an embodiment of the present invention. The system block diagram can be, for example, an Internet Protocol Television (IPTV) system platform 100. The IPTV system platform 100 mainly includes a Central Management Unit 102, a Live Streaming Server 104, and Intellectual Property Management and Protection (IPMP) terminal user 106. The IPTV system platform 100 is a video system 100.

The central management unit 102 includes a digital rights management server (DRM Server) 102a responsible for digital rights management, and a user database for recording user information (including user accounts, passwords, and user profiles) (User Database). 102b, a service management server (Service Management Server) 102c responsible for service management, and a service management database 102d for storing digital multimedia program forms. The instant streaming server 104 is a source of the multimedia content 104a, and its functions include encoding, packetization, streaming of the source content, and a digital rights management server (DRM Server) 102a. The common key (Common Key, CK) is provided to encrypt the multimedia content to be transmitted, and to detect the bandwidth capability of the user before transmitting the multimedia content; in other words, the instant streaming server 104 is A multimedia content delivery device. The Intellectual Property Management and Protection (IPMP) end user 106 is authenticated by a Digital Rights Management Server (DRM Server) and has a client that can receive multimedia stream rights, and is given a decoding and decryption function, that is, wisdom. The Property Rights Management and Protection (IPMP) end user 106 is a multimedia content receiving device.

The operation process of the IPTV system 100 described above is as follows: First, the account application and registration: the user account and password are registered to the digital rights management server (DRM Server) 102a of the central management unit 102 through a web browser. Then, the user login (Login): the user's personal account and password will be encrypted by the RSA encryption algorithm, and then transmitted to the digital rights management server (DRM Server) 102a and verified by the user identity to ensure transmission. The security of the data in the process. Then, the user identity authentication (Authorization): after receiving the user's account number and password, the digital rights management server (DRM Server) 102a restores the protected data, and then through the user database (User Database) 102b ratio User identification for the user. Secondly, the available bandwidth estimation (Available Bandwidth Estimation): the available bandwidth estimation (Available Bandwidth Estimation) is provided by the real-time streaming server 104 to provide different bandwidth capabilities according to the user. A suitable service within the user's rights. Finally, display playback (Display): After the bandwidth estimation, select the best quality program file suitable for the bandwidth stream playback and play.

Referring to FIG. 1 , FIG. 2 and FIG. 3 , FIG. 2 is a flow chart showing a hierarchical available bandwidth estimation method of the video system 100 in the embodiment of the present invention, and FIG. 3 is a diagram of the present invention. A schematic diagram of a hierarchical available bandwidth estimation mechanism in an embodiment of the invention. As shown in FIG. 2, and with reference to FIG. 3, the hierarchical available bandwidth estimation method of the present invention is applicable to a video system 100 having a transmitting device 104 and a receiving device 106, which includes the following steps:

In step S200, the transmitting device 104 selects a first detection bandwidth range 200a between the first lower bandwidth threshold (Bmin1) and the first upper critical bandwidth value (Bmax1), and the first detection The bandwidth range 200a is composed of a complex bandwidth 202. In an embodiment, the first detection bandwidth range 200a may be divided into a bandwidth of K equal parts, wherein the first lower bandwidth threshold (Bmin1) and the first upper critical bandwidth (Bmax1) The unit can be, for example, Mbps (Mega-bits per second), K is a positive integer, and the bandwidth of each aliquot can be expressed by the following formula (1):

Brange=(Bmin1-Bmax1)/K......(1)

In step S202, the transmitting device 104 initializes a probe packet sequence 204 according to the first upper bandwidth threshold and the first downlink bandwidth threshold of the first detection bandwidth range 200a, so that the detection packet sequence is 204 includes a plurality of packet groups 206, each packet group 206 corresponding to a bandwidth 208, each packet group 206 corresponding to a detection rate 210, and each packet group 206 is composed of a plurality of detection packets 206a composition. In one embodiment, the ith detection rate Ri of the detection packet 206a in the detection packet sequence 204 of the hierarchical available bandwidth estimation (HABE) method of the present invention is expressed by the following formula (2):

Ri=Bmin+i*Brange,i=1,2,...,K...(2);

In an embodiment, the detection rate Ri of the packet group 206 is selected from the bandwidth 202 corresponding to the packet group 206.

Next, determining the time interval T between the detection packets 206a, the size of the detection packet 206a used by each detection rate Ri can be obtained by the formula (2), and N indicates the number of detection packets 206a of each packet group 206. The detection rate refers to the amount of data sent by the transmitting device 104 in a unit time, and the unit thereof is, for example, the number of bits per second (bps), which can be expressed by the following formula (3):

Li=Ri*T, i=1, 2,...,K...(3);

According to formula (3), the size of the detection packet 206a (the number of bits included in the detection packet 206a) can be changed, or the time interval between the detection packet 206a and the detection packet 206a can be changed (the number of bits per unit time) ) to determine the detection rate.

The packet delta value ΔP between each probe packet 206a is expressed by the following formula (4):

ΔP=Li+1-Li, i=1, 2,..., K-1...(4)

In step S204, the transmitting device 104 can transmit the probe packet sequence 204 to the receiving device 106 via the network 103.

In step S206, the receiving device 104 calculates the one-way path delay of each detection packet 206a according to the transmission time of the detection packets 206a from the transmission device 104 and the reception time to the receiving device 106 (One- Way delay, OWD). In an embodiment, a transmission path PA is formed between the transmitting device 104 and the receiving device 106, and at least one node (for example, a router) 105 is disposed on the transmission path PA, and each unidirectional path delay is defined. The processing delay, the Queing delay, the transmission delay, and the Propagation delay of the slave node 105 for each probe packet 206a in the node 105 of the transmission path PA. The sum of the four.

In step S208, a delayed cumulative turning point 207 is determined according to the unidirectional path delay of each detecting packet 206a and a second detecting bandwidth range 200b is formed in the first detecting bandwidth range 200a, wherein the second The detection bandwidth range 200b is smaller than the first detection bandwidth range 200a, and the second detection bandwidth range 200b includes a second upper bandwidth threshold Bmax2 and a second lower critical bandwidth value Bmin2. Specifically, the hierarchical available bandwidth estimation (HABE) method of the present invention analyzes and judges one-way using a Pairwise Comparison Test (PCT) and a Pairwise Difference Test (PDT). Whether the path delay (OWD) has an Increasing Trend (indicated by "I"), a Non-increasing Trend (indicated by "N"), and an Ambiguous Trend (using " A" indicates), and then find the turning point at which the cumulative delay begins. In a preferred embodiment, each of the probe packets 206a can be subjected to a PDT test such that the unidirectional path delay (OWD) has more sample values, thereby improving the accuracy of the determination.

When judging which area the user's available bandwidth (OWD delay cumulative turning point) falls in, it is mainly to observe the results judged by the two methods of reference PCT and PDT, and finally the final trend judgment result (Trend). In the judgment, first look from the far right to the left, find the first N, as the next critical bandwidth value of the next probe, and then look back from this N to the right, find the first I, Taking the upper bandwidth threshold as the next detection, indicating the turning point 207 of the OWD delay accumulation, that is, the available bandwidth BA of the user, is roughly in the range of the upper and lower bandwidth thresholds N to I found. Inside, then proceed to the next probe.

In step S210, comparing the second detection bandwidth range 200b with a predetermined bandwidth, when the second detection bandwidth range 200b is less than the predetermined bandwidth, the frequencies in the second detection bandwidth range 200b The width 202 is calculated to form an available bandwidth BA as shown in step S211; when the second detection bandwidth range 200b is greater than the predetermined bandwidth, step S212 is performed. In an embodiment, when the second detection bandwidth range 200b is less than a predetermined bandwidth, the available bandwidth is equal to an average of the second upper bandwidth threshold and the second lower threshold bandwidth. , wherein the available bandwidth BA is expressed by the following formula (5):

BA=(Bmin2+Bmax2)/2......(5)

The above available bandwidth BA is defined as the amount of data that can be transmitted by the transmitting device 104 before the transmission path is less than a specific delay value, and the available bandwidth BA can be utilized by the hierarchical available bandwidth estimation method of the present invention. The bandwidth capability is defined as the maximum amount of data that can be transmitted in a unit of time in a transmission path, that is, the maximum amount of data that the receiving device 106 can receive per unit time.

In step S212, the probe packet sequence 204 is re-initialized according to the second probe bandwidth range 200b, and step S204 is continued until the available bandwidth BA is formed. In other words, according to the transmission time and the reception time in each detection packet 206a, the one-way path delay (OWD) of each detection packet 206a is calculated, and the inflection point at which the unidirectional path delay starts to accumulate is analyzed, which are two Between the detection rates Ri, and transmitting the two detection rates Ri information back to the transmitting device 104, the transmitting device 104 sets the two detection rates Ri as the new upper bandwidth threshold and the new detection bandwidth range. Lower critical bandwidth value. Then, a hierarchical available bandwidth estimation (HABE) detection packet sequence 204 is designed to perform the next stage of detection, so that the detection is repeated until the lower critical bandwidth value (Bmin) and the upper bandwidth threshold (Bmax). ) is in a convergent state and covers a range of detection bandwidths less than a predetermined bandwidth to form the available bandwidth BA.

Referring to FIG. 4A and FIG. 4B, FIG. 4A is a schematic diagram showing the design of a packet sequence of the first hierarchical available bandwidth estimation in the embodiment of the present invention. FIG. 4B is a schematic diagram showing the trend analysis of the unidirectional path delay according to FIG. 4A in the embodiment of the present invention. In Fig. 4A, K=50, N=5, the hierarchical available bandwidth estimation detection packet sequence 204, and the detection packet 206a is transmitted at a time interval T=1 ms, so the hierarchical available bandwidth estimation The detection range (Bmin, Bmax) of the detected probe packet sequence 204 is (0 Mbps, 10 Mbps). The determined probe packet sequence 204 is then transmitted to the receiving device 106 where the predetermined bandwidth is set to 200 kbps.

After receiving the detection packet sequence 204 of the hierarchical available bandwidth estimation completely, the receiving device 106 calculates the unidirectional path of each detection packet 206a according to the transmission time and the reception time of the detection packet 206a in the detection packet sequence 204. Delay (OWD), and then based on the calculated one-way path delay of each probe packet 206a, and analyze and determine the turning point at which the delay starts to accumulate to obtain a new bandwidth detection range (Bmin, Bmax) = (4M, 6M) And the new bandwidth range is transmitted back to the transmitting device 104, and the one-way path delay (OWD) trend analysis is as shown in FIG. 4B.

Specifically, when performing trend analysis, the PCT and PDT methods are used, and any method can be used for judgment. However, when using both methods at the same time, it is more accurate to judge whether there is an upward trend. If both PCT and PDT methods are judged to have an upward trend (indicated by I) in the same region, the final trend judgment result (Trend) in this region has an upward trend (indicated by I); similarly, if PCT and Both methods of PDT are judged to have no upward trend (indicated by N) in the same region, and the final trend judgment result (Trend) in this region has no upward trend (indicated by N); but if PCT and PDT are two ways One of the judges has an upward trend (indicated by I), and the other judges that there is no upward trend (indicated by N), and the final trend judgment result (Trend) of this region is an ambiguous region (indicated by A).

Referring to FIG. 5A and FIG. 5B, FIG. 5A is a schematic diagram showing the design of a packet sequence of the second hierarchical available bandwidth estimation in the embodiment of the present invention. FIG. 5B is a schematic diagram showing the trend analysis of the unidirectional path delay according to FIG. 5A in the embodiment of the present invention. Since there is no "N" in the Trend set in Figure 5A, we set the lower bandwidth Bmin to the minimum 4M (4.4 M "A" area is negligible), and the upper limit Bmax is set to "I" of 4.8 M. . Therefore, a new bandwidth detection range (Bmin, Bmax) = (4 M, 4.8 M) is obtained, and then the new bandwidth range is transmitted back to the transmitting device 104.

Referring to FIG. 6A and FIG. 6B, FIG. 6A is a schematic diagram showing the design of a packet sequence of the third hierarchical available bandwidth estimation in the embodiment of the present invention. FIG. 6B is a schematic diagram showing the trend analysis of the unidirectional path delay according to FIG. 6A in the embodiment of the present invention. As shown in Fig. 6B, this available bandwidth estimate yields a new bandwidth detection range (Bmin, Bmax) = (4.48 M, 4.8 M) and then passes back the new bandwidth range to the transmitting device 104.

Referring to FIG. 7A and FIG. 7B, FIG. 7A is a schematic diagram showing the design of a packet sequence of the fourth hierarchical available bandwidth estimation in the embodiment of the present invention. FIG. 7B is a schematic diagram showing the trend analysis of the unidirectional path delay according to FIG. 7A in the embodiment of the present invention. The new bandwidth detection range (Bmin, Bmax) = (4.48 M, 4.608 M) (4.54 M of the "A" area is negligible, so select 4.48 M). Since Bmax-Bmin=4.608 M-4.48 M=126 K, which is less than the set predetermined bandwidth=200 K, the bandwidth detection is ended, and the available bandwidth A=(Bmax+Bmin)/2=(4.48) is obtained. M+4.608 M)/2=4.544 M.

In summary, the present invention discloses a hierarchical available bandwidth estimation method, which uses a detection packet sequence including a complex detection rate to effectively reduce the bandwidth estimation time; each detection rate uses multiple packets. In order to make the accumulation of the unidirectional path delay more obvious, it is easy to confirm the turning point position; and the hierarchical detection method is used to estimate the bandwidth capability of the end user to accurately measure the bandwidth range of the end user.

While the invention has been described above in terms of the preferred embodiments, the invention is not intended to limit the invention, and the invention may be practiced without departing from the spirit and scope of the invention. The scope of protection of the present invention is therefore defined by the scope of the appended claims.

100. . . IPTV system platform

102. . . Central management unit

102a‧‧‧Digital Rights Management Server

102b‧‧ User database

102c‧‧‧Service Management Server

102d‧‧‧Service Management Database

103‧‧‧Network

104‧‧‧ Instant Streaming Server

104a‧‧‧Multimedia content

105‧‧‧ nodes

106‧‧‧Intelligent property management and protection of end users

200a‧‧‧First detection bandwidth range

200b‧‧‧second detection bandwidth range

202‧‧‧width

204‧‧‧Detection packet sequence

206‧‧‧Packet group

206a‧‧‧Probing packets

207‧‧‧ Delayed cumulative turning point

FIG. 1 is a block diagram showing a system for performing a hierarchical available bandwidth estimation method in an embodiment of the present invention.

2 is a flow chart showing a hierarchical available bandwidth estimation method of a video system in an embodiment of the present invention.

FIG. 3 is a schematic diagram showing a hierarchical available bandwidth estimation mechanism in an embodiment of the present invention.

FIG. 4A is a schematic diagram showing the design of a packet sequence of the first hierarchical available bandwidth estimation in the embodiment of the present invention.

FIG. 4B is a schematic diagram showing the trend analysis of the unidirectional path delay according to FIG. 4A in the embodiment of the present invention.

FIG. 5A is a schematic diagram showing the design of a packet sequence of the second hierarchical available bandwidth estimation in the embodiment of the present invention.

FIG. 5B is a schematic diagram showing the trend analysis of the unidirectional path delay according to FIG. 5A in the embodiment of the present invention.

FIG. 6A is a schematic diagram showing the design of a packet sequence of the third hierarchical available bandwidth estimation in the embodiment of the present invention.

FIG. 6B is a schematic diagram showing the trend analysis of the unidirectional path delay according to FIG. 6A in the embodiment of the present invention.

FIG. 7A is a schematic diagram showing the design of a packet sequence of the fourth hierarchical available bandwidth estimation in the embodiment of the present invention.

FIG. 7B is a schematic diagram showing the trend analysis of the unidirectional path delay according to FIG. 7A in the embodiment of the present invention.

Claims (10)

A hierarchical available bandwidth estimation method for use in a video system having a transmitting device and a receiving device, the hierarchical available bandwidth estimating method comprising the following steps: (a) the transmitting device selects one a first detection bandwidth range, where the first detection bandwidth range is between a first lower bandwidth threshold and a first upper critical bandwidth, and the first detection bandwidth ranges from a plurality (b) the transmitting device initializes a detection packet sequence according to the first upper bandwidth threshold and the first downlink bandwidth threshold of the first detection bandwidth, the detection packet sequence Include a plurality of packet groups, each of the packet groups corresponding to one of the bandwidths, each of the packet groups corresponding to a detection rate, and each of the packet groups is Composed of a plurality of detection packets; (c) the transmitting device transmits the detection packet sequence to the receiving device; (d) the receiving device according to the transmission time of the detection packets from the transmitting device, and arrives at the receiving device Receiving time, to count a one-way path delay of each of the detection packets; (e) determining, according to the one-way path delay of each of the detection packets, a delay cumulative turning point and forming a first one of the first detection bandwidth ranges a second detection bandwidth range, wherein the second detection bandwidth range is smaller than the first detection bandwidth range, and the second detection bandwidth range is between a second upper bandwidth threshold and a second lower threshold bandwidth a range between the values; (f) comparing the second detection bandwidth range with a predetermined bandwidth, when the second detection bandwidth range is less than the predetermined bandwidth, the range of the second detection bandwidth Calculating in the bandwidth to form an available bandwidth, and when the second detection bandwidth is greater than the predetermined bandwidth, performing step (g); (g) reinitializing the probe packet sequence in accordance with the second probe bandwidth range and proceeding to step (c) until the available bandwidth is formed. The hierarchical available bandwidth estimation method according to claim 1, wherein when the second detection bandwidth range is less than the predetermined bandwidth, the available bandwidth is equal to the second upper bandwidth threshold and The average of the second lower critical bandwidth value. The hierarchical available bandwidth estimation method according to claim 1, wherein each of the bandwidths is equal to a difference between the first upper bandwidth threshold and the first lower threshold bandwidth. , divided by the number of these bandwidths. The hierarchical available bandwidth estimation method according to claim 3, wherein the detection rate is related to the first lower critical bandwidth value and the bandwidth. The hierarchical available bandwidth estimation method according to claim 4, wherein the size of each of the detection packets is related to the detection rate and a time interval between the detection packets. The hierarchical available bandwidth estimation method according to claim 5, wherein a difference in size between each of the adjacent detection packets is defined as a packet increment value. The hierarchical available bandwidth estimation method according to claim 5, wherein a transmission path is formed between the transmitting device and the receiving device, and at least one node is disposed on the transmission path. The one-way path delay is defined as the sum of the processing time, the queuing time, the transmission time, and the time of pushing the network time for each of the detection packets in the node of the transmission path. The hierarchical available bandwidth estimation method according to claim 1, wherein the detection rate of the packet group is selected from the bandwidth corresponding to the packet group. The hierarchical available bandwidth estimation method according to claim 1, wherein in the step of determining the delayed cumulative turning point and forming a second detection bandwidth in the first detection bandwidth range, The delayed cumulative turning point of the one-way path delay is determined by a pairwise comparison test and a pairwise difference test analysis. The hierarchical available bandwidth estimation method according to claim 9, wherein in the step of determining the delayed cumulative turning point and forming a second detection bandwidth in the first detection bandwidth range, The pairwise comparison test and the pairwise difference test analysis are used to determine whether the one-way path delay has an upward trend, no upward trend, and an ambiguous trend to find the delayed cumulative turning point.