See discussions, stats, and author profiles for this publication at: https://www.researchgate.net/publication/3867419
`
`A fast method to optimise network resources for video-on-demand
`transmission
`
`Conference Paper  in  Conference Proceedings of the EUROMICRO · February 2000
`
`DOI: 10.1109/EURMIC.2000.874665 · Source: IEEE Xplore
`
`CITATIONS
`8
`
`2 authors:
`
`Enrique Hernandez-Orallo
`Universitat Politècnica de València
`
`91 PUBLICATIONS   1,262 CITATIONS   
`
`SEE PROFILE
`
`READS
`25
`
`Joan Vila
`Universitat Politècnica de València
`
`74 PUBLICATIONS   319 CITATIONS   
`
`SEE PROFILE
`
`Some of the authors of this publication are also working on these related projects:
`
`My doctoral thesis View project
`
`Automated Contingency Management in Unmanned Aircraft Systems View project
`
`All content following this page was uploaded by Enrique Hernandez-Orallo on 16 September 2016.
`
`The user has requested enhancement of the downloaded file.
`
`Petitioner's Exhibit 1105
`Google LLC v. WAG Acquisition, IPR2022-01413
`Page 0001
`
`

`

`A Fast Method to Optimise Network Resources for Video-on-Demand Transmission Enrique Hernández Orallo Bancaja ehernandez@bcj.gbancaja.com Joan Vila-Carbó Dpto. de Informática de Sistemas y Computadores jvila@disca.upv.es Abstract1 The transmission of video on demand (VoD) will become one of the most successful services in Internet. This implies the playback of stored video over a high-speed network with a strict quality of service (QoS). Guaranteeing this QoS requires a very demanding reservation of network resources. That makes optimisation of network resources a key issue. This paper introduces a fast method to optimise network reservations based on the concept of empirical envelope. Previous works faced this issue either using smoothing techniques to reduce peak rates, or in a costly iterative way based on jointly adjusting encoding and channel rates that cannot be efficiently used at transmission time. The proposed method is based on generating a set of points from the stored video with an off-line analysis of its empirical envelope, and then using these points to efficiently calculate the optimal reservation for a given channel, at channel establishment time. The paper shows that the number of points generated is very low making this approach very efficient. 1. Introduction Media-on-demand (video, audio, …) will become a usual service in Internet in the near future. This will allow a customer, for example, to select a movie from a server in order to watch it on-line, similar as today’s pay-per-view TV. For VoD, it can be assumed that media is stored on a server, and clients can request them via a network channel for continuous playback. The success of these services relies on the ability to guarantee a QoS, and the approach to provide it is based on reserving network resources [14][15]. These reservations are often very demanding, so optimisation becomes a key issue. Figure (1) depicts the scenario for VoD. There is a 1This work has been supported by the Spanish Government Research Office (CICYT) under grant TIC99-1043-C03-02 media server with a set of disks where the media is stored. When a client wants to see a film, it connects to the server and selects the desired film. At this moment, a real-time channel, with a specified QoS, is established and video frames flow through this channel from server to client. Channel establishment requires reserving some network resources (bandwidth and buffers) in order to implement the real-time channel. This reservation mainly depends on traffic characteristics, but also on network parameters. If the video is stored in the server, then all traffic characteristics are known when the transmission starts. However, channel parameters are usually known at channel establishment time. A problem that arises when transmitting video, is how to estimate the parameters of a traffic model for a given workload. Traffic is usually VBR (Variable Bit Rate), and it is sent through channels with a flow model that limits transmission rates. One of the most used traffic models is the leaky bucket. An upper bound for the end-to-end delay time for this flow model, as a function of the reserved bandwidth and the network parameters, can be estimated using equations as the ones by Parekh/Gallager [3][4]. Aiming at multimedia transmission through Internet, IETF has been working in the specification of a set of protocols for integrated services (IntServ) [17]. More specifically, the RSVP protocol has been introduced for network resource reservation [1]. This protocol defines a guaranteed quality of service [2], based on a token bucket description of the flow. Out buffersHigh-SpeedNetworkDisk storageNetwork InterfaceMedia ServerClient bufferClientsFigure 1 : Video on demand
`
`Petitioner's Exhibit 1105
`Google LLC v. WAG Acquisition, IPR2022-01413
`Page 0002
`
`

`

`=
`
`+
`
`+
`
`+
`
`>
`
`- --
` (1) )(rpRDRCMQtottotdelay ‡‡
`
`+
`
`=
`
`+
`
` (2) where Ctot,Dtot are the parameters defining the network, p,r,b,M are the traffic flow parameters, R is the bandwidth reservation in the network and Qdelay the end-to-end delay. Parameters Ctot and Dtot can be calculated for a WFQ scheduling algorithm as follows. First Ci and Di are estimated for every link. Di is made equal to the MTU (Maximum Transmission Unit) of the link divided by the link bandwidth, with the condition that M (Maximum datagram size) must be smaller than the minimal MTU of the path. Value Ci is assumed M in order to consider packet fragmentation. The required buffer size at the nodes is b+Csum+Dsumr where Csum y Dsum are the sum of all previous Ci y Di parameters. A simpler equation that not depends on the peak rate to obtain the end-to-end delay is the one by Parekh and Gallagher, usually used for nodes with WFQ schedulers (some other schedulers use this equation too: Virtual Clock, WF2Q, FFQ, SPFQ [5]). If the source traffic is constraint by a leaky bucket (
`
`,r )
`
`s
`
` flow then the maximum end-to-end delay is: )(max1
`
`s
`
`+
`
`=
`
`+
`
`r
`
`s
`
`+
`
`=
`
`+
`
`=
`
`Several works about how to optimise video quality and network resources using a leaky-bucket flow model have been reported in the literature. The goal of those works [10][12] is to obtain optimal encoding algorithms by selecting jointly the encoding and channel rates. Other techniques are based on smoothing the VBR video in order to reduce the peak rate. Smoothing can be achieved by sending data ahead of schedule. Some works present optimal smoothing algorithms for some given network parameters such as the bucket depth or the bandwidth reservation [9][13]. However, optimisation can be also done using a two-step procedure instead of a joint optimisation [16]. According to this, encoding rates can be optimised without explicitly considering the actual channel rates, solely for the purpose of achieving optimal video quality. Once the encoding rates are chosen, the rate channel can be selected to optimise the network resources. This paper advocates this approach and introduces a very fast method to obtain the optimal transmission rates. QoS requires estimating resource reservations when a new channel is being established. The amount of reservations is a function of the specific connection parameters and the traffic characteristics. The problem is how to obtain the flow model parameters from a traffic workload in order to optimise the reserve of network resources. This can be done using an iterative and costly process based on scanning the video every iteration and for every transmission. Usually, the reservation is calculated approximately [6]. This paper proposes an alternative approach to obtain this optimal reservation based on the concept of empirical envelope. The approach comprises two phases. During the first phase, the video is analysed off-line in order to obtain its empirical envelope and to extract a reduced set of points of this envelope. The second phase occurs at channel establishment time and, at this point, the former set of points is used, together with channel parameters, to estimate the optimal reservations. The paper also shows that the flow parameters that make reservations optimal are the same for the delay equations of Parekh/Gallager and IETF/RSVP guaranteed service using a WFQ class scheduler. This results a simplification of the calculus for IETF/RSVP and in an extension of the results to both models (leaky bucket and token bucket). The set of well-known MPEG-1 traces studied by O. Rose [8] will be used throughout this paper. 2. Obtaining the end-to-end delay The end-to-end delay bound of a packet can be calculated defining a network and flow model, and it is a function of the reserved bandwidth in the links. The IETF specification for a guaranteed service uses the token bucket (b,r,p) traffic model where the number of bits that the source transmits is less than b+rt, for any interval of time t with peak rate p. The maximum end-to-end queuing delay bound can be calculated using these equations: )()())((rRpDRCMrpRRpMbQtottotdelay ‡
`
`RDRCCLRnLDelaytottotnjjjii (3) where Li is the maximum packet size for session i, Lmaxj is the maximum packet size in node j, Cj the bandwidth of the link j and n the number of nodes. This equation is equivalent to (1) when the peak rate p is infinite (the r and b parameters are equivalent to
`jLi. It is important to recall that the network minimal latency must be added to equations (1)(2)(3) in order to obtain the complete delay. This latency is usually negligible compared to network delay. Since the goal is to calculate the reservation for a given delay, equations (1) and (3) can be written as: )())(())(()(rRpMbrpDQrpCMpMbRtotdelaytot ‡
`RDDCRtottot (5) Shortly, to calculate the networks reservations it is necessary: (1) a network model, to obtain the Ctot, Dtot and M parameters already determined, and (2) the calculation of the flow parameters (b,r,p) or (
` in order to optimise network resources2. 2 We will use
`
`+
`
`+
`
`+
`
`>
`
`-- -
` (4) )(
`‡--
`
`r
`
`s +
`
`=
`
`=
`
`s
`
`s ,r
`
`, Li = M and Lmaxj = MTUj). The buffer size in the j node is
`
`s ,r
`
`). From these parameters, obtaining the peak rate is straightforward. The problem is how to calculate parameters
`r
`
`s
`
`s ,r
`
` to denote the leaky bucket and b,r token bucket parameters.
`
`Petitioner's Exhibit 1105
`Google LLC v. WAG Acquisition, IPR2022-01413
`Page 0003
`
`‡
`(cid:229)
`-
`-
`and
`

`

`r )
`
`and D2(
`
`r )
`
`r )
`
`in the numerator are greater than the terms of the denominator. That is: p > 1 : It is obvious that the transmission rate is greater than 1bit/s (M+Ctot)>(Qdelay-Dtot) : That is the first condition. (cid:240)(cid:240) The two conditions of this lemma are usually satisfied. In the first one, (M+Ctot) is a multiple of M that is the maximum packet size that is usually greater than (Qdelay-Dtot) that has a maximum value of the demanded delay and is mostly a reduced value (less than 10 seconds). The second is an obvious condition because the buffer in the node at least is M to store the maximum message. Given that R(
`
`r )‡
`
`is decreasing and that condition p>R(
`r
`must be satisfied, it can be stated that the optimal reserve is when R(
`
`r .
`
`r
`
` Therefore, this is the convergence criteria. This criteria has a very important consequence: Corollary 1: The
`values that optimise the reservation in equation (4) optimise equation (3) too. Proof: Given that the convergence criteria is R(
`r
`r
`, then if R is put in place of
`+=
`r in equation (1) yields: rRDRCbDtottot ‡
`+
`
`s
`
`r
`
`r =
`
`s
`
`"i. The value of
`
`s
`
`£
`
`i
`
`r
`
`s (r )
`
`r
`
`for a leaky bucket flow model, so this formula can be minimised. This conveys an analysis that starts by estimating the bucket fullness of the leaky bucket model. Assume that encoded video sequences have n frames and the number of encoded bits produced by frame i is Ei. If the flow source is constrained by a leaky bucket, then it cannot transmit more than
` Considering f frames per second, and ignoring the finite capacity of the bucket, then the bucket fullness (in bits) at the end of frame period i is [13], },0max{1fEiii
`- (6) The traffic would comply with this if the bucket capacity
`0max)( (7) Figure (2a) shows the called LAMBS traffic that is part of the “Silence of the Lambs” movie, which has 1500 frames. Figure (2b) shows the bucket fullness (the values of
`yield different bandwidth reservations for the same traffic. Equation (4) can be used to optimise the reservation using, for example, an iterative method to find the values of
`
`represent decreasing functions. A sufficient condition for function to be decreasing is that the terms that multiply D1(
`that is the same equation (3) developed by Parekh/ Gallager. (cid:240)(cid:240) 01000020000300004000050000600007000080000900001000000100200300400500600700800900100011001200130014001500Frame NumberFrame Size (bits)(a)01000020000300004000050000600000100200300400500600700800900100011001200130014001500Frame NumberCumulative bits(b) Figure 2 : (a) LAMBS Traffic (b) bucket fullness Link BW (Mbps) MTU (bits) l1 10 10000 l2 15 12000 l3 20 15000 l4 10 20000 n1n2n3SenderReceiverl1l2l3l4 M = 10000 m = 1000 Figure 3 : Sample network
`
`r
`
`s (r )
`
`and it is a decreasing function. Although
`is not a continuous function, since it uses integer numbers, it can be modified to use real number returning a real value of
`
`s .
`
` a function that calculates the reservation R depending on
`can be estimated:
`rs
`r
`=
`
`+
`
`r
`
`+
`+
`
`rs
`
`>
`
`r
`
`r
`
`r
`
`r )
`
`-- -
`)()())(())(())(()(RpMpDQpCMpMRtotdelaytot(8) Lemma 1: R(
` is a decreasing function in the domain [0,p ] if the following conditions are true: (M+Ctot) > (Qdelay-Dtot) and
`
`s
`
`s (
`
`s (
`
`> M Proof: Provided that
`t)-M is decreasing too by condition
`is always less than p, and then p-
`is decreasing too. Therefore, R(
`r
`
`r
`s
`
`r
`
`r )
`
`+
`D-
`
`r
`r
`
`=
`
`+
`
`r )
`
`r )
`
`r
`D D
` can be written as: )()()()()()()(2121
`r
`totdelaytotDQCMpR where D1(
`+
`y D2(
`
`3. Optimising bandwidth reservation The goal of this section is to obtain an expression of the bandwidth reservation R as a function of
`
`r
`
`s +r t
`
`bits at time t, so the drain rate is
`
`r .
`
`=
`
`s
`
`+
`
`rs
`
`=
`
`s
`
`£<
`
`ini
`
`s
`
`s
`
`s
`
`r :
`
`s
`of 1Mb/s. It easy to check that different values of
`
`s ,r
`
`i) in every frame period for a drain rate
`
`r
`
`s
`r
`
`r
`
`that optimise this reservation, as suggested in [16]. The value of
`
`r
`
`s
`
`Petitioner's Exhibit 1105
`Google LLC v. WAG Acquisition, IPR2022-01413
`Page 0004
`
`-
`is chosen such that
`
`can be thus written as a function of
`and
`ranges from 0 to p. The value of
`depends on the value of
`Replacing in (4) r by
`and b by
`‡
`-
`-
`p) is decreasing,
`> M. Given that
`D
`
`) =
`and
`) =
`
`

`

`r
`
`This corollary implies that using the established convergence criteria for the reservations given by the two equations are the same. That supposes that the more complex traffic model specification of the RSVP/IETF guaranteed service is not necessary to obtain the optimal reservation in case that all the routers use WFQ class schedulers. Since the RSVP/IETF delay equation is based on the C and D parameter of the nodes, equation (8) should be used in case that some node does not use this class of scheduler. This paper will make use of equation (3). Working out the value of R in this equation and replacing
`
`s (r )
`s
`
`r
` the following function that calculates the reservation R depending on
`
`r
`
`=
`
`r )
`
`r )
`
`is decreasing in the domain [0, p] Proof: Given that
`is decreasing and the other elements are constants, R’(
`
`s (r )
`
`rs
`+
`r
`‡-
`)(')()('RDDCRtottot (9) Lemma 2: R’(
`is decreasing. (cid:240)(cid:240) It is important to determine the range of values that make R’(
`
`r )
`
`r )
`
`=r :
`
`r
`
` Lemma 3: R’(
`
`r )
`
` if pDDCtottot £-. Proof: Given that the range of
`
`r ,
`
`r )
`
`r
`
`s (r )
`
`s (r )
`
`r )
`
`r )
`
` it should take a value in the range [p,0]. Since R’(
`, that is decreasing too, the minimal value of R’(
`
` However, this calculation is still costly and the traces generated must be stored in a huge file. Therefore, this is a non-viable method at channel establishment. A fast and bounded method is needed at this time. 4. A new method to optimise network reserve As seen in the last section, it is necessary to obtain the values of
`
` is 0, that is: tottotDDC-; so this implies that the greatest value in the interval [0,p], that is, p is tottotDDC- at least. (cid:240)(cid:240) If this condition is not satisfied, it is necessary to reserve a higher bandwidth than the peak rate in order to transmit with the demanded delay. In this case, an equation like (2) should be used so it does not depend of the traffic characteristics. An iterative method can be used to find a solution of equation (9). Using this, the parameters that make optimal the reservation for the example of the beginning of this section, for a delay of 0.1s are
`
`" t
`
`‡
`
`s ,r
`
`s ,r .
`
`0E+02E+64E+66E+68E+61E+71E+71E+72E+72E+70100200300400500600700800900100011001200130014001500Frame NumberCumulative bitsCumulative arrivalsEmpirical envelope Figure 4 : LAMBS Traffic : functions A(t) and empirical envelope
`
`s
`
`r
`
`= 50208b, yielding in a bandwidth reservation of 944590b/s. The problem is that this method is very costly and it is not bound. For every iteration, the video must be scanned to obtain
`For example, for the LAMBS traffic, 20 to 25 iterations must be done before the solution is found, depending on the required delay. It is obvious that it can be optimised generating a video trace with the objective of calculating
`
`s
`
`s .
`
`r .
`
`r
`
`s
`
` that optimise resource reservation, that is, equation (3). This section proposes an alternative and fast method based on the concept of the empirical envelope. Although the cost of generating the empirical envelope is high, it has the advantage that this task can be done off-line for each video once in a lifetime. From the empirical envelope, an algorithm to obtain the envelope points is devised. Using these points, a quick way to optimise the reserve is described. 4.1. Empirical envelope The Tenet group [11] introduced the concept of the empirical envelope E(t) in order to define a time invariant bound of the traffic. If a channel traffic is given by function A, such that A[
`
`t ,t +
`
`,t +
`
`£
`t ,t
`
`‡
`
`t
`t] denotes the traffic arrivals in a time interval [
`t], then function A*(t) will be an upper bound on A if the following holds: A[
`A*(t) for all
`t
`
`0. Any function A*(t) that satisfies this property is referred as a traffic constraint function. Such a function provides a time-invariant bound on A, so the traffic is bounded for every interval of length t. The empirical envelope E(t) of an arrival function A is defined as the most accurate traffic constraint function, where, the following holds A*(t)
`>0. Figure (4) illustrates the former defined functions A(t) and empirical envelope E(t) for the LAMBS traffic. Any straight line l(t) that contains the empirical envelope will define the
` leaky bucket parameters and by definition it will bound the traffic as can be seen in figure (5). This figure shows that for the same empirical envelope two straight lines l1(t) y l2(t) can be fitted giving two pairs of values
`
`Petitioner's Exhibit 1105
`Google LLC v. WAG Acquisition, IPR2022-01413
`Page 0005
`
`by
` yields:
`
`
` converge, that is, to satisfy condition R’(
`
`
`converges to
`is [0,p], if R’(
`
`converges to
` is decreasing and only depends on
`is when
`= 944590b/s and
`for a drain rate
`and
`+t]
`
` E(t)
`

`

`s 2+
`
`r 2
`
`l1(t)=
`
`s 1 +r 1tE(t)l2(t)=
`
`s
`
`bitst Figure 5 : Fitting straight lines into the envelope As described in section 3 the bucket depth
`
`r .
`
`is function of the traffic and the rate drain
`For example, given the following traffic { 1, 2, 0, 4, 2, 0, 1}, the
`r
` rates{ 2, 1, 0.5, 0.25 } are { 2, 4, 6.5, 8.25 }. Therefore, each value of
`
`s
`
`r
`
`s ,r
`
`defines a traffic constraint function l(t). Figure (6) shows the empirical envelope of the given traffic and the straight lines l(t) derived from the
`values. These lines touch the empirical envelope without cutting it. According to the definition of the empirical envelope, every straight line l(t) that touches it will be the best approximation to the traffic and the y-intercept will be
`
`s .
`
`r t,
`s
`
`‡
`" t
`
`r
`
`=
`
`s
`
` (11) 01234567891011012345678tbitsr=2r=1r=0.5r=0.25Figure 6 : Envelope and some l(t) functions. Real traffics are discrete, that is, there are a set of values Ei for a fixed times t, so E(t) can not be derived to obtain the tangent lines. Condition (10) implies that if a straight line touches a point ti it cannot cut function E(t). Let l-(t) be the straight line with lower slope that touches the empirical envelope in a previous point and l+(t) the straight line with greater slope that touches the empirical envelope in a posterior point. The condition is that there is not a previous point ti-1 where the slope of l-(ti-1) was greater that the slope of l-(ti) and no later point where the slope of l+(ti+1) was lower than l+(ti). Figure (7a) shows these two lines. (cid:239)(cid:238)(cid:239)(cid:237)(cid:236)
`
` The desired goal is to obtain the complete set of these lines. The figure suggest the method: the straight lines only touch the empirical envelope in some given points: 1,2,5 and 7. These points, the envelope points, will be used to obtain the set of lines l(t). 4.2. A method to calculate the envelope points According to last section, the envelope points can be used to calculate all the straight lines l(t) that best fit the empirical envelope. If the traffic is described by a function l(t)=
` any function l(t) (l*(t) is the set of all these lines) must contain E(t). That is: 0)()(* ‡"‡ttEtl (10) The line l(t) will be a good approximation if the difference between l(t) and E(t) is minimal. Therefore, l(t) will touch (without cutting it) at least in a point of E(t). If E(t) were a continuous function, the tangent lines would be calculated for any value of t. However, although E(t) is an increasing function E’(t)>0
`0, it is not true that the slopes are decreasing. This implies that there are straight lines that cut E(t) and condition (10) it is not satisfied. The tangent lines will not cut a function in a defined interval if the function is concave down. If E(t) was a down concave function then all the lines l(t) would be obtained depending of t: ttEtEttEttEt)(')()()();(')( -
`
`s ,r
`
`r i
`
`) are obtained to construct a piece-wise linear concave upper approximation to E(t) and can thus be policed with a n-level leaky bucket. The complexity of this algorithm is the same: O(n*m) where n is the number of frames and m the obtained points. L-(t)L+(t)E(t)titoti-1ti
`
`r i
`
` Figure 7 :(a) Lines L- y L+ , (b) Decreasing slopes
`
`=
`
`r
`
`=
`
`=
`
`+
`
`<
`>
`
`=
`=
`
`r
`r
`r
`
`
` >> -- -"11iiiit
`
`
`
`+
`
`r
`r
`"‡(cid:222)
`--)()()()()()(tEtltttEtltttEtliiiiiiii
`r
`r
`"£
` (12) Shortly, we want to obtain the points of E(t) where the slope of the straight line that joins with previous points are always decreasing, as shows figure (7b): -
`+
` Using this condition, an algorithm to calculate the envelope point has been devised as detailed in figure (8). This algorithm, although different, generates the same points than the one developed in [11]. In this article a set of parameters (
`
`Petitioner's Exhibit 1105
`Google LLC v. WAG Acquisition, IPR2022-01413
`Page 0006
`
`values for the following
`+
`
`-
`-1
`

`

`r(t) is [p,0], we have to proof that do not exist another straight line l’(t) with the same slope that satisfies l’(t)<l(t). By condition (12) the straight line l(t) touches the empirical envelope at least in one point ti. If another straight line l’(t)<l(t) exists with the same slope
`
`and then the reservation must be calculated directly using equations (4) and (5). INPUT : Network parameters Ctot and Dtot. Envelope points ti,pi,Ei i = 0..n OUTPUT:R,
`, s : Bw. reservation and flow parameters. i0 = 0; i1 = n; do // 1 Finds the interval iiio=
`+
`12;
`s
`i); RCDDtottot
`=
` if R <
`r
`r
`i then i0 = i; if R >
`i then i1 = i; while (i1 - i0) > 1; // 2 Calculate the R and
`+
`values RECDDtitottoti
`=
`=R; Figure 9 : Algorithm to calculate the optimal bandwidth reservation
`
`+-
`
`(r
`s '
`s
`
`r
`
`= Ei - R*ti;
`
`;s
`
`+
`
`s
`
`s
`
`i-1,
`
`0(p)=0 and
`
`r
`
`r ,
`
`<s .
`s ’
`
` this will imply that
`
` It means that the value of l’(t) in ti is smaller than l(ti). Given that l(ti)=E(ti) this means that l’(t) cuts the empirical envelope not satisfying the condition (10). Given that by lemma (4)
`) is continuous and monotonous decreasing we can obtain all the straight lines l(t) for each value of
`r(t) is the set of all them. (cid:240)(cid:240) The fact that L
`r(t) is the set of closest straight lines to the empirical envelope implies that
`s
`gives the same values of the equation (7), so it can be used to found the roots of equation (9) in an iterative way. Nevertheless, we can use a fast and straight method. If the root R=
`
`(r
`s ’
`
`r )
`
`r .
`
`r
`
`r
`r
`is in the interval [
`rs
`i ], we have that: iiiRttE -=
`
` and replacing
`
`i-1,
`
`s
`
`by this expression into (9) and working out the value of R yields: itottotitottotiitDDCtERDDCRttER
`+
`(cid:222)-
`
`=
`
`+
`
`+
`
`=
`
`)()( (16) so we can obtain the value of R directly. The method consists in a binary searching for the interval where the solution is and then apply equation (16). In figure (9) is described the algorithm to find the solution. This algorithm found the solution very fast and is bounded, so it has a cost of O(log m) where m is the number of points. The buffer reservation at nodes can be calculated using the equations described in point 2. If a restriction is imposed on the buffer sizes, this implies a limit in the value of
`
`INPUT: to..tn : traffic time interval E(t) : Empirical envelope. OUTPUT: ti ,pi, Ei: points, slopes and E value at ti m : Number of points obtained 010100)()(,0tttEtEt --
`// First point t1 = 1; i = 1; for t between t1..tn 11)()( - ---
`iitttEtEr while r >= pi-1 // Remove Last point i = i - 1;11)()( - ---
`iitttEtEr end while if r < pi-1 then // New point ti = t;
`
`= r
`
`=
`
`=
`
`r
`
`=
`
`i-1 = r; i = i + 1; Ei = E(t); End if End for m = i; Figure 8 : algorithm to get the envelope points 4.3. Getting the set of closest straight lines l(t) Given a point i, the value of
`
`r
`
`s
`
`r
`r
`i ]. The value of
`
`i-1,
`
`is the y-intercept of all the straight lines that touch this point: iiittE
`rs
`r
`=
`)()( (13) and then
`rs
`rs
`r
`r
`r
`=
`‡‡
`is given by: iii
`-1)()(' (14) that means, that first the interval of
`has to be found and then apply the equation (13). Lemma 4:
`is monotonous decreasing and continuous in the interval [0, p ]. Proof: Function (13)
`s
`r
`r
`is monotonous decreasing because only depends on
`s
`s
`i ]. The value of E(t0) is the peak rate so
`m(0)= E(tm) when
`r
`is 0. By definition the straight line that touches the point ti with slope
`i-1 also touches the point ti-1 and therefore have the same value in the origin
`s
`r
`r
`s
`r
`s
`r
`i) and
`
`i(
`
`i)=
`
`i+1(
`
`is continuous. (cid:240)(cid:240) The range of
`in the domain [0, p ] is [0, T ] where T is the sum of all the bits transmitted (that is the value E(tn) ). Let L
`r(t) be the set of straight lines l(t) obtained for any value of
`{
`}
`rs
`r
`r
`
`
`
`pttltL ££= = +
`r
`0)()()( (15) Theorem 2: L
`r(t) is the set of closest straight lines to the empirical envelope E(t). Proof: If the slope range of L
`
`r )
`
`i(
`
`(r )
`s ’
`
`r
`
`s .
`
`i-1)=
`
`i-1(
`
`i-1). For
`
`i is the same, so
`
`(r )
`s
`
`r
`
`r
`
`(r
`s i
`
`(r )
`s ’
`
`(r )
`s ’
`
`r .
`
`Petitioner's Exhibit 1105
`Google LLC v. WAG Acquisition, IPR2022-01413
`Page 0007
`
`is in the interval [
`-
`in the interval [
`So
` That is:
`So L
`’(
`)()(
`-
`-
`=
`-
`

`

`Summing up, the whole process is outlined in figure (10) and consists in two independent phases. The first phase, that is the most time consuming, can be done in the moment the video is introduced in the server. The second phase starts when a channel is being established to start the video transmission. In detail: PHASE I: The goal is to obtain the envelope points from the stored video. For this: (a) the empirical envelope is calculate from the video, (b) using the algorithm (8) the envelope points are generated and stored in a file associated with the video. The most costly process of this phase is the calculation of the empirical envelope: O(n2). There are other more efficient algorithms, but this is not relevant because is an off-line process. PHASE II starts when a channel is going to be established to transmit the stored video. In this phase: (c) a client request a video using a channel with a certain characteristics, (d) in the server using the algorithm (9), the optimal reserve for the network is calculated using the known network parameters and the envelope points associated with the video and (e) the network resources are reserved beginning the video transmission. The cost for obtaining the optimal reserve is O(log m). 5- Some results over MPEG videos In this point, we show some results over some MPEG video traces. For this, we have implemented the algorithms to obtain the envelope points and the optimal reserve. As a consequence of corollary (1), the reserves are equivalent for the IETF/RSVP and Parekh/Gallager equations. For example, the generated points for the LAMBS traffic are in the figure (11). Note that one of the most interesting properties of these points is that gives a synthesized description of the traffic. This way the first value of
`is always the peak rate p. High-SpeedNetworkDisk storageNetwork InterfaceMedia ServerClient(a)(b)(c)(d)(e) Figure 10: A two phases process 0200000040000006000000800000010000000120000001400000016000000180000000100200300400500600700800900100011001200130014001500Env.Points n T(s) rr(b/s) n T(s) rr(b/s) 0 0 2199800 1224 48.96 202511.11 1 0.04 523966.67 1260 50.4 200883.33 13 0.52 506206.67 1272 50.88 199058.33 73 2.92 414816.67 1296 51.84 190000.00 85 3.40 300400.00 1320 52.8 165933.33 87 3.48 275088.89 1356 54.24 158866.67 96 3.84 259243.57 1368 54.72 154190.48 780 31.2 249333.33 1452 58.08 117883.33 792 31.68 244450.00 1464 58.56 105800.00 804 32.16 242122.22 1476 59.04 102166.67 840 33.6 239033.33 1488 59.52 36466.67 852 34.08 235898.72 1491 59.64 30266.67 1164 46.56 227933.33 1497 59.88 19000.00 1176 47.04 215408.33 1499 59.96 0 1200 48 203091.67 Figure 11: Envelope points for LAMBS traffic Using these points with the network of figure (3), for a delay of 0.1s a reservation of 944590b/s is calculated with the pair values
`
` decrease exponentially until 0.25s to later decrease lineally. Using the complete SOCCER traffic (40000 frames, about half an hour) 37 envelope points are obtained. The minimal demanded delay is 0.014s, so figure (13) shows the optimal reserve for delays between 0s to 5s. The results are very similar than the last ones 020000040000060000080000010000001200000140000000,511,522,533,544,550500000100000015000002000000250000030000003500000s(b)R(b/s)ssR= rr Figure 12: Optimal bandwidth reservation and bucket depth for LAMBS traffic.
`
`r =
`
`s =
`
`s
`
`944590b/s. By lemma (3) the minimal permitted delay can be calculated as D=Ctot/p+Dtot=0.023s. Figure(12) shows the bandwidth reservation R and the bucket depth
`as a function of the demanded delay ranging from 0 to 5s. The less is the demanding delay the more the value of
`is, because the frames have to be stored in the network. The increase of
`r
`
`s
`
`s
`
`r
`
`Petitioner's Exhibit 1105
`Google LLC v. WAG Acquisition, IPR2022-01413
`Page 0008
`
` 50208bits and
`versus time is quite lineal. On the other hand,
`

`

`that optimise the resource reservation of the network. It is based on generating the envelope points from the empirical envelope. This process is done off-line using the stored video. With these points, a fast and bound method to calculate the optimal reservation is described. In the moment of establishing the channel the computational cost of obtaining this optimal resource is bounded to log m where m is the number of points and is very low (< 100 in the samples studied) confronted with the not bounded cost of the iterative method: O(log n*i) where i are the iterations needed to find the solution. These new method can be applied to any network that uses a leaky bucket or token bucket traffic model. There are many schedulers than use this model (WFQ, Virtual Clock, WF2Q, etc) and the IETF guaranteed service for RSVP too. A mechanism to use this new method has been proposed for use in media-on-demand servers. A derived conclusion of the