UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Design and Performance of a Continuous Media Server for a High-Speed Network Sonah, Bikash 1994

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-ubc_1995-0076.pdf [ 2.5MB ]
Metadata
JSON: 831-1.0064921.json
JSON-LD: 831-1.0064921-ld.json
RDF/XML (Pretty): 831-1.0064921-rdf.xml
RDF/JSON: 831-1.0064921-rdf.json
Turtle: 831-1.0064921-turtle.txt
N-Triples: 831-1.0064921-rdf-ntriples.txt
Original Record: 831-1.0064921-source.json
Full Text
831-1.0064921-fulltext.txt
Citation
831-1.0064921.ris

Full Text

Design and Performance of a Continuous Media Server for a High-Speed Network by Bikash Sonah B. Sc. (Electrical Engineering) University of Manitoba A THESIS SUBMITTED IN PARTIAL F U L F I L L M E N T OF T H E REQUIREMENTS FOR T H E D E G R E E OF M A S T E R OF APPLIED SCIENCE in T H E F A C U L T Y OF G R A D U A T E STUDIES DEPARTMENT OF E L E C T R I C A L ENGINEERING We accept this thesis as conforming to the required standard  T H E UNIVERSITY OF BRITISH C O L U M B I A Dec. 1994 © Bikash Sonah, 1994  In  presenting this  degree at the  thesis  in  University of  partial  fulfilment  of  of  department  this thesis for or  by  his  or  scholarly purposes may be her  representatives.  It  is  permission.  of  *~  e  c  v  The University of British Columbia Vancouver, Canada  Date  DE-6 (2/88)  ;  for  an advanced  Library shall make  it  agree that permission for extensive  publication of this thesis for financial gain shall not  Department  requirements  British Columbia, I agree that ,the  freely available for reference and study. I further copying  the  U  granted  by the  understood  that  head of copying  my or  be allowed without my written  Abstract In this thesis we present two multimedia architectures and a data retrieval model for supporting simultaneously multiple clients requesting files of different playback rates. After reviewing some theoretical background from previous research, we study the performance of the architectures in terms of the maximum number of concurrent video streams they can support using circular SCAN disk scheduling policy. We present new techniques, namely, the maximum operation set and the Rate-based Buffer Weighting Scheme, not only to adapt the system to streams of different playback rates but also to relieve the processing load on the server. Next, we devise a new way of designing the Admission Control for both architectures. The new Admission Control is simple, effective and efficient. Finally we compare the merits of the architectures in terms of throughput, contention, client buffer size and reliability.  ii  Contents Abstract  ii  List of Figures  vii  Acknowledgment Chapter 1  viii Introduction  1  1.1  Objectives  1  1.2  Motivations  2  1.3  Contributions  3  1.4  Assumptions  3  Theoretical Background  5  2.1  Safe Operation Set  5  2.2  Quality Proportional Multi-Subscriber Scheme  7  2.3  Rounding Operation  8  Chapter 2  Chapter 3  System Modelling  10  3.1  System Architecture  10  3.2  File Storage  12 iii  3.3  Data Retrieval Model  13  3.4  V M E Interrupt bus  16  3.5  Client Buffering Requirements  17  3.6  Circular Scan Disk Scheduling Policy  20  3.7  Interfile Seek  20  3.8  Worst-case Interfile Seek  23  3.9  Determining Time to Perform Operation Set  24  Performance Analysis  26  4.1  Admission Control  26  4.2  Minimum Operation Set  27  4.3  Maximum Operation Set  29  4.4  Finding the Maximum Operation Set  30  4.5  Performance  33  Design of New Admission Control: Architecture I . .  38  5.1  Problems of Dynamic Playback Constant  38  5.2  Rate-based Buffer Weighting Scheme  39  5.3  Choosing the Rate-based Buffer Weight Constant . . .  41  5.4  Maximum Operation Set Size  42  Chapter 4  Chapter 5  5.5  • Admission Control iv  45  Chapter 6  Design of New Admission Control: Architecture II. .  48  6.1  Stream Admission  48  6.2  Choosing the Rate-based Buffer Weight Constant . . .  48  6.3  Drive Maximum Operation Set Size  49  6.4  Maximum Operation Set Size  51  6.5  Admission Control  53  Further Discussions  57  7.1  Comparing Architectures  57  7.2  Admission Control Additional Features  58  7.3  Limitations  59  7.4  Relaxing the Assumptions  60  Related Work  62  Chapter 7  Chapter 8 8.1  Storage Techniques For Digital Continuous Multimedia  62  8.2  Disk Arrays  63  8.3  Streaming RAID  63  8.4  Caching Strategies  64  8.5  Admission Control Algorithms  65  8.6  Statistical Control Admission  66  v  8.7  Scheduling Policies with Batching  67  8.8  Scheduling Policies for Multimedia Services  68  8.9  Lancaster Continuous Media Server (LCMS)  69  8.10  Mutimedia Storage Server (MSS)  70  8.11  Gopher-style Real-time A T M Multimedia Services (GRAMS).  71  Conclusions  73  9.1  Contributions  73  9.2  Choice of Architecture  74  9.3  Future Work  75  Chapter 9  Bibliography  76  vi  List of Figures Figure 3.1  Server Servicing Multiple Clients  10  Figure 3.2  Server Architecture  11  Figure 3.3  Node Architecture  11  Figure 3.4  Figure Data Retrieval Model  15  Figure 3.5  Double Buffering  19  Figure 3.6  Rounding Operation  19  Figure 3.7  Seek Time versus Distance Travelled  22  Figure 3.8  Interfile Seek Scenarios  22  Figure 4.1  Absorption Elasticity due to Slack Time  30  Figure 4.2  Calculating the Maximum Playback Constant  32  Figure 4.3  Performance of Architecture I  35  Figure 4.4  Performance of Architecture II  37  Figure 5.1  Effectiveness of Admission Control  47  Figure 6.1  Effectiveness of Admission Control (Random Files Requests)  Figure 6.2  55  Effectiveness of Admission Control (Severe Contention)  56  vii  Acknowledgment I would like to thank my supervisor, Dr Mabo Ito, and my co-supervisor, Dr Gerald Neufeld, for giving me the freedom, the guidance and the encouragement to investigate into issues where I felt room for improvement exists. I should also thank my supervisors for their time and efforts they took in understanding the materials to the depth I did and in helping me in the correction and editing of the literature. I am also grateful to Mark McCutcheon, Rob Ross, Jeffrey Chow, John Tanlimco and Peter Meisl for their assistance whenever I wanted it., Their information at hand and their suggested books and reading materials were greatly appreciated. Finally, I would like to thank The Lord, without Whose intelligence and resources, this project would not concretize. This project is more one of insights than one of hard work or past experience. This work was funded by Canadian Institute for Telecommunications Research.  viii  1 Introduction 1.1 O  b  j  e  c  t  i  v  e  s  In recent years, the technological world has witnessed an increase in speed of CMOS technologies, in transmission bandwidth and in storage capacity. Moreover, services that were analog are now stored in digital form. These technological improvements and the advantages of statistical sharing have increased efforts towards integrating services. However, disk data rates have not increased as rapidly and have become a central issue in designing multimedia systems. This thesis focuses on the design and performance analysis of a multimedia server built from existing drive systems.  This multimedia server is intended  to service simultaneously a large number of clients requesting different media of different rates.  The multimedia server should guarantee that each stream  be provided data at an average rate equal to its playback rate so that playback proceeds at real-time. Our objectives are to: to design two disk layout architectures that can support multiple client streams simultaneously. to analyze performance and identify bottlenecks. to develop techniques for supporting concurrent streams of different playback rates. 1  to design simple Admission Control schemes for both architectures, to compare the two architectures.  1.2 Motivations This thesis addresses many problems found in previous work. These problems are listed as follows: •  A n analysis is made on a multimedia server assuming a high disk rate and considering only disk parameters. However, to achieve this high disk rate, other architectural components such as buses or intermediate buffers come into play. These components introduce parameters which must be considered to reflect a more realistic world. The existing Admission Control scheme guarantees no starvation in steady state only. However, when a new stream is accepted, its absorption may result in starvation.  Moreover the elasticity added in the system is most  suitable for the unique case in which all streams are the same. When a new stream is accepted, the data load to be retrieved for existing streams is likely to change, resulting in a need for transitions. Transitions constitute a heavy processing load on the server. The maximum number of streams admitted by the Admission Control may not correspond to the maximum throughput at the server. For instance, any 2  client may limit the performance of the server to a value below its maximum throughput, by subscribing with a small buffer.  1.3 Contributions The scope of the thesis is as follows.  After reviewing some theoretical  background reached by previous research we present two multimedia server architectures, built from existing technologies, and a data retrieval model, which is simplified but realistic. We analyze the performance of the architectures in terms the number of concurrent video-rate streams they can support. We also present a new technique (that is, finding the maximum operation set) that makes absorption of accepted streams more elastic. Third, we present a new scheme, called the Rate-based Buffer Weighting Scheme, in which the load of data retrieved for existing streams remain fixed even though a new stream is accepted or an old stream dies.  This scheme eliminates the necessity for transitions. Fourth, we  devise a new way of designing a simple yet effective Admission Control for the server architectures presented. The maximum number of streams admitted corresponds to the maximum throughput at the server. Finally, the merits of both architectures are compared.  1.4 Assumptions Our study is based on the following assumptions:  •  The granularity of a stripe is chosen to be one track. Therefore, zero-latency read is possible. A linear seek-time-versus-distance-travelled model is used. Delays at switches and propagation delays are not considered. Blocks are retrieved without errors.  4  2 Theoretical Background 2.1 Safe Operation Set The server operates in cycles. In each cycle, the server delivers a load of data in a burst for each stream into its buffer, a load of data being the the number of blocks the server retrieves for each stream. While a stream is playing back one load of data, the server ensures delivery of another load of data within the cycle. Suppose the server has admitted n clients. The server services each stream S\, S2,  S  n  in a service round [1] [2] by reading k\, & 2 , k  of the files F i , F 2 , F  n  called the  media blocks  with constant playback rates Ri, R 2 , R n .  {Si, i = \..n} is known as the  operation set,  n  stream set.  The set  The set {hi, i = l..n} is known as the  where kj, the number of blocks to be retrieved for stream j, is  operation for  that stream.  Let the size of buffer at the client i be denoted as B{.  Then a feasible  operation set is one in which  kiU <Bt  1 = l..n  (2.1)  where U is the size of the media block. The number of blocks the server reads for each client should not overflow the buffer available at the client. The above equation is known as the  feasibility criterion. 5  Let the time for the server to retrieve k blocks for the stream i be denoted as t  L{ki) and the cycle time as r . Then a continuous operation set is one in which  the time to perform the operation set I is  T / 7  .  rain ( hU']  1=1  v  J  The quantity k{U jR{ is the playback duration that the server gives to client i in each cycle. The above equation simply says that the time for retrieving blocks for all the streams should be less than the minimum playback duration of all the streams. The stream that has the minimum playback duration is called the critical stream, because it determines the cycle time r and the operation set. The above equation is also known as the continuity criterion. If wi(t) denotes the number of blocks remaining at the buffer of client i, where 0 < wi(t) < k over time t, then the remaining playback duration Wi(t) x  at time t for that stream is given by  W,(t) =  (2.3)  A stream is said to starve if Wi{t) = 0 during any cycle. A safe operation set is one in which no stream starves. Past literature [1] made the following very important claim about a safe operation set: Claim  A feasible and continuous operation set is a safe operation set. 6  Proof When the client buffer is filled, the client gets the maximum playback duration. Therefore, using the feasibility and continuity criteria,  wr {t) = f>-£->Y. ^) x  L  i=l  =  l  Now, because the client gets a load of data every cycle, W{{i) > 0 during any service round.—i  2 . 2 Q u a l i t y P r o p o r t i o n a l M u l t i - S u b s c r i b e Recall that the server retrieves k\, & 2 , k Si,S2,...,S  n  with playback rates R\, R2,...,  n  block units for the streams  Rn- The simplest operation set would  be a fixed number of block units, say K, for all the streams no matter what how different their playback rates are. By substituting K in the continuity criterion, that is,  we notice that the streams whose playback rates are smaller than ? [Ri] have m  x  more data blocks retrieved in a cycle than they really need. This simple operation set results in the server admitting fewer streams than optimum. The Quality Proportional Multi-Subscriber Scheme (QPMS) [2] finds this optimum operation set by proposing that the higher the playback rate of a stream, 7  the more data block units the server should retrieve for that stream. In other terms, hi oc Ri or ki = K,R{  (2.4)  where K is a constant of proportionality which we will call the  playback constant.  The continuity criterion therefore becomes I=  T  i=i  /  L( Ri) K  <  min ( .  i  \  KRilJ}  I Ki  \ =KII  )  = T.  (2.5)  Furthermore, the playback durations the clients get are equalized and are given by  hU  —-  tii  KR,U = —-—  = KU  . I = L.re.  (2.6)  -Kj  From (2.5) and (2.6), each client gets a playback duration equal to the cycle time. This is the optimization that QPMS brings to the operation set.  2 . 3 R o u n d i n g  O p e r a t i o n  If the playback constant is a fraction, so are the operations k{ = uRi  i = l..n.  Since we are reading whole values of U, in our model we shall make the operationsintegral, that is, k{ = \KR[\  i = l..n  (2.7)  and modify the feasibility and continuity requirements accordingly. This modification is still correct because the playback duration each stream gets is definitely greater or equal to the cycle time, that is,  ^L> U K  Ri  = r.  (2.8)  In other words, the number- of blocks retrieved for a stream is  a little more than  what is really needed. The server shall rectify this by rounding down the operation to [nRi\ in some cycles along the retrieval process so that on average the client gets nR{ media blocks per cycle [2].  9  3 System Modelling  3.1 S  y  s  t  e  m A  r  c  h  i  t  e  c  t  u  r  e  As shown in Figure 3.1 , the multimedia server services several clients across an A T M network. The server architecture is shown in Figure 3.2. The nodes are identical and communicate with the manager microprocessor via an ethernet bus. The node architecture is shown in Figure 3.3. In the next section, we present two variations of the server architecture. The major difference among them is in the way the files are stored.  Client 1 Client 2  ATM Network  Client n  Figure 3.1 Server Servicing Multiple Clients  10  Nodel Atm Fibre Link Peak Rate: 140 Mbps Design Rate: 124.4 Mbps  622 Mbps ATM switch  Node 2  Node 3  ATM switch  Node 4  Node 5 Microprocessor Ethernet Bus  Figure 3.2 Server Architecture  2 MB Buffer 100 kB buffer ATM  2 GB main memory  SCSI Host  SCSI Host  Microprocessor  SCSI DC  SCSI DC  SCSI DC  SCSI DC  SCSI DC  SCSI DC  o o uo  80 MHz 64MBps VMEbus Ethernet  20 MBps SCSI bus  O disk-arrayi  SCSI Host SCSI DC  SCSI DC  Figure 3.3 Node Architecture 11  SCSI DC  3 . 2 F i l e  S t o r a g e  Architecture I (Striping) Each file is striped along  N  disks in a contiguous  fashion. The striping granularity is a whole track length, UT, which will be called a block sub-unit. For example, the first stripe of a file is on the first drive at some cylinder location, the second one on the second drive at the same cylinder location, . . ., the N  TH  (N + l)  th  one on the N  IH  drive at the same cylinder location, the  one back on the first drive but on the next cylinder location, and so  on. Therefore, the size of media block unit is  U = NU  T  (3.1)  The reason for choosing the striping granularity to be a whole track length is to make zero-rotational-latency read possible. As soon as the head reaches the desired cylinder location, the disk controller (DC) can start reading and buffering data in its random access memory. Other drives can be hooked in parallel to the SCSI buses to mainly increase the file storage capacity of each node. Each node may therefore have several disk arrays each of N disks. Indeed, a row of drives can be viewed as a single large drive.  Architecture II (No Striping) In Architecture II, files are not striped among disks but are stored in a contiguous fashion. The size of the media block unit 12  in this case is  U=U  T  (3.2)  3 . 3 D a t a R e t r i e v a l M o d e l To retrieve a media block from the node, the node microprocessor sends to all the SCSI hosts a command to read a track or block sub-unit. The transfer of a block sub-unit from a particular drive across the buses and the intermediate buffers to the client is summarized in Figure 3.4. Some typical parameters are listed in Table 3.1.  The drive parametres are from the drive system Seagate  ST12400N/ND. First, the microprocessor requests the VME bus. Upon getting the bus, the microprocessor sends a read command to a particular SCSI host and releases the bus. In turn, the SCSI host requests the SCSI bus, gets it, sends a read command to a particular D C and disconnects from the SCSI bus. The D C makes a seek, and buffers a block sub-unit at its memory. It then arbitrates the SCSI bus and the SCSI host allows a reconnection. The transfer of the block sub-unit from the DCs buffer to the SCSI host's buffer then takes place. Upon receiving a block sub-unit, the SCSI host interrupts the microprocessor. An interrupt latency is encountered before the microprocessor responds.  The  microprocessor saves the context, and goes into polling the SCSI hosts using a rotating priority scheme.  Upon identification of the interrupt source, the 13  microprocessor can initiate another read at that SCSI host.  It then initializes  registers of the D M A C at that SCSI host and releases control of the V M E bus to the D M A C . A D M A burst transfer takes place from the SCSI host's buffer to the main memory, after which the microprocessor is again interrupted. Once the block sub-unit reaches the main memory and provided the buffer at the A T M interface is not full, the microprocessor initializes the D M A C at the A T M interface for another D M A burst transfer from the main memory to the buffer at the A T M interface. To signal the end of transfer, the A T M interface interrupts the microprocessor. The A T M interface transfers the block across the switch.  After the transfer, the A T M interface interrupts the microprocessor to  indicate the availability of buffer.  Minimum Seek, S  1 ms  Maximum Seek, SM  19 ms  Revolutions Per Minute  5411  Track Capacity, UT  43 kB  Cylinders, CM  2621  Interrupt Latency  200 us  Saving Context  200 Instructions  Polling a Device  2 Instructions  Cell Header Overhead  5 B  M  Table 3.1 System Parameters  14  « H  Si to  < .s 9  43  OH  O  H U  O  to  o  •3  p  ID  ,"3  O S  M o  (D  £ 11  6 Q  o -S  11 :§ | g <5  PH  ^  ^  P — < 5  O  s  Q  g • O o E- OO  to  to  2 S,  -  N  ' <a a  • -  1  OH  on  .5  s  Q.S  2 OH  E  00  * H  O  ^  3.Q  00  T3 to  a>  4>  cr . J2  15  S  'PS  3.4 V M E Interrupt bus Whether or not the files are striped among several drives, the V M E bus must be fair to all the SCSI hosts attached to it, or else the one with the lowest priority interrupt may have a poor access to the V M E bus.  Unfortunately, the V M E  interrupt bus, which is made of seven interrupt lines, has a fixed priority scheme. Moreover, the other available option, daisy chaining, is "biased" to the devices located early on the daisy chain. However fairness can be established by software by making all SCSI hosts interrupt on a single interrupt line and by using a rotating-priority polled interrupts scheme.  While software polling scheme is usually slow and inefficient, polled  interrupts scheme is not. Once an interrupt occurs, polling is used only to identify which device has pulled the interrupt line low. Other devices contending for the V M E , such as the A T M interface, the Ethernet interface, can interrupt the microprocessor on other interrupt lines. The interrupt lines must be properly allocated to the devices and properly disabled by the microprocessor such that  no device can preempt a D M A burst transfer once it starts. the microprocessor manager has a fast access to the V M E bus and thus to the node microprocessor for communication purposes.  16  3.5 Client Buffering Requirements  A media block unit is striped among several disks in parallel. When a media block unit is being retrieved, the media block sub-units (or stripes) may reach the client buffer in a random chronological order. This represents a synchronization problem if clients have FIFO buffers. We circumvent this synchronization problem by using random-access memory (RAM) at the client. Moreover, because the data retrieval model is quite complex, predicting exactly when in a cycle the media block sub-units may reach the client buffer is impossible. Therefore a stream may starve even though it is given a playback duration equal to or slightly greater than the cycle time. Noting that within a cycle the client shall receive a load of data in accordance to the continuity criterion, we can avoid the danger of starvation by using double buffering at the clients.  That is, the R A M buffer size at the client should be  twice the load of data it gets in a cycle. We suggest that the client should start playback only at the beginning of the second cycle, after it has buffered its first load of data. While the client is playing back one load of data (stored in the first buffer), it has enough buffer space (the second buffer) to buffer another load of data which is expected within the cycle. At the end of the cycle, the first buffer becomes free, while the second buffer continues the playback. Continuity of data is thus preserved as can be seen in Figure 3.5. 17  A client may require one extra block of buffer because of rounding operations. Because operations are rounded up, a client effectively receives a playback duration  a little greater than the cycle time, that is, a client obtains an extra  fraction of a block. This extra data accumulates cycle after cycle. When close to one block of data is in this way accumulated, the server then rounds the operation down. The extra block of buffer is needed to accommodate the extra block a client accumulates; Figure 3.6 depicts the importance of an extra block of buffer at the client. The unrounded operation is 3.8. The rounded-up and rounded-down operations are 4 and 3 respectively.  18  1  St  cycle  2nd cycle  {/////////\  3rd cycle  f  /////////////>,  time  Figure 3.5 Double Buffering  cycles  1  2  3  4  5  6  # blocks retrieved  4  4  4  4  3  4  # blocks played back  0  3.8  3.8  3.8  3.8  3.8  0.2  0.4  0.6  0.8  0.2  0.4  4  4.4  4.6  4.8  4  4.2  up  up  up  up  # blocks in excess # blocks at end of cycle rounding up/down  Figure 3.6 Rounding Operation  19  down  up  However, without loss of generality, we shall continue to use single buffering in the analysis.  3.6 C  i  r  c  u  l  a  r S  c  a  n D  i  s  k S  c  h  e  d  u  l  i  n  g P  In this policy [6], the disk head generally scans in one direction, from the outermost toward the innermost tracks, reading tracks for the streams in the order of the scan direction. In the next cycle, the scan direction is reversed, that is from the innermost toward the outermost track. This policy is called Circular Scan (CSCAN). Overlapping files may cause a slight deviation from the above policy. At the beginning of each cycle, the server reorders the streams in accordance to the cylinder location of their reads within each disk-array. The order in which streams are serviced changes with cycles for the following reasons. Firstly, the scan direction switches back and forth from cycle to cycle. Secondly, because of different operations and because files are located on different platters, the head position for a higher-rate stream may pass the position for a lower-rate stream. Stream set reordering poses no starvation threat if double buffering is used at the clients. The following two sections aim at finding the worst-case interfile seek for C S C A N disk scheduling policy.  3.7 I  n  t  e  r  f  i  l  e S  e  e  The measured seek-time-versus-distance 20  k curve typically [4] looks like that  o  l  i  c  y  shown in Figure 3.7. We consider a simple model where seek time is linear with the distance that the head travels, after an initial start-up time S . m  Our simple  model uses the minimum seek time and the maximum seek time given in the drive specifications.  An interfile seek is a seek from the last track that the head has just read for the previous stream to the first track that the head should read for the next stream. There are two scenarios for interfile seeks as shown in Figure 3.8. In the first scenario, the tracks that the head should read for any two streams i — 1 and i do not overlap in cylindrical location. After performing the operation for stream i — 1, the head travels a few cylinders, say di, along the scan direction to the desired track at which it can perform the operation for stream i.  In the second scenario, the tracks that the head should read for two streams overlap in cylindrical location.  This overlap can occur because the files are  physically located on different platters and may overlap vertically. Overlap can also occur because the two streams request the same file with very small phase difference. In both cases, as the head finished the operation for stream i — 1, it has to retract a few cylinders (of course smaller than or equal to  in the direction  opposed to the scan direction before performing the operation for stream i.  If d denotes the distance in cylinders, then from Figure 3.5 the interfile seek 21  is given by  Figure 3.7 Seek Time versus Distance Travelled  platters  'i-l  platters  k  F. 1  E — »  Figure 3.8 Interfile Seek Scenarios 22  3.8 W  o  r  s  t  -  c  a  s  e I  n  t  e  r  f  i  l  e S  e  e  k  Let 6 be a subset of the operation set whose operations involve seeks with no overlap. Assume the node has only one disk array. The total time a drive spends on seeking in a cycle is given by n  Ts = ^2[S ,  +  f l  (k -l)S ] l  m  i=i  E  n Q(UO overlap)  ied  ^(overlap)  •  = Y (Sm ied /  V~"^ / ,  ) + Y, ( m i o' S  d = d t  >.  »=1  itO' + AS  1  + S < A  d  f  i e'  k i  n ) + £ (** " l ) S m i=l  i=l  e  The total number of cylinders the head travels over in a cycle can never be greater than the maximum number of cylinders of the drive, plus twice the sum of the cylinders the head retracts. Thus, T  s  < AS  d = C M  +2(J]  j + ]T  AS < d  n  kt  ice'  }  kiS  m  i=i n  < AS  d = C M  + 2[J]  AS  . n < AS = d  CM  + 2 HP  j +  d = k i  \ Z^  =  f  c  \ i = l  = (S - S ) + ( E  ,  hS n  + £ /  fc,-5  m  »=1  -™)) + E « <  2  M  m  S  m  23  fc  5  If M' denotes the number of disk-arrays from which streams are requesting files, then by inspection,  T  s  <  |M'(5  m  -S ) m  + ^ S  m  +  2 ^ J 2 ~  Sm)^  | +  J2(*« -  ^  (3.4) Let 7j be a subset of the stream set whose streams correspond to the files physically located in the disk-array j and let /(•jj) denotes the first stream, in the scan direction, of the subset jj. _.S  m  + (SM + S ) tn  Jm  Then, a worst-case model for the interfile seek is + %(S  + -Q^\OM  M  -Sm),i  ~ bm),  = f(i ),j J  =  l..M  otherwise  3.9 D e t e r m i n i n g T i m e t o P e r f o r m O p e r a t i o n S e The time to perform the operation set is determined by simulation.  The  buses, namely, the SCSI buses, the V M E bus and the A T M fibre link, and the intermediate buffers, namely, the SCSI host's buffer, the main memory and the ATM interface's buffer are modelled as resources. The queue model for the queues at the resources, except the SCSI bus, is First-Come-First-Serve. The queue at the SCSI bus is a priority queue because the SCSI bus has a fixed priority scheme. The transfer of a media block sub-unit from the drive to the client is modelled as a process named Read_a_block. Some important parameters that the process uses are: •  the interfile seek time and the minimum seek time 24  the time a block sub-unit is read and buffered at the D C the time durations for a block sub-unit be transferred from the D C to the SCSI host, from the SCSI host to the main memory, from the main memory to the A T M interface, and from the A T M interface across the A T M switch to the client. interrupt latencies At the beginning of the simulation, TV Read_a_block processes are created because of N parallel drives. During the simulation, without going into details, each of those processes will recursively generate at appropriate events a total of n  h identical Read_a_block processes inclusive. Processes make requests for i=i  the resources, suspend themselves for some amount of time, are suspended if resources are held, are reawakened if resources become free. The simulation ends when all Read_a_block processes die. / is the time from the beginning of the simulation to the end of the simulation. If we use the worst-case model for the interfile seek, the I obtained from simulation is also worst-case. Therefore, we need to determine I by simulation only once to test if the operation set is continuous.  25  4 Performance Analysis 4 . 1 A d m i s s i o n  C o n t r o l  Architecture I If a node has n streams running with the two safety requirements satisfied, that is,  kiU = KKiU  < B{  i = l..n,  and  i=i  v  y  and if a new stream S^+i with playback rate R +i n  subscribes, then the server  can accepts the stream only if a new playback constant k! exists such that the two safety requirements are still satisfied, that is,  K'R.U^B,  i = l..n + l ,  and n+l  J^L^'Ri) i=i  < K'U.  Architecture II In Architecture II, the drives in fact operate independently, each servicing a small set of streams. In other words, each drive w has a stream set of streams and an associated playback constant  depending on n& . Each  drive can be thought of as a "mini-node" within a node. 26  w  Say a new stream requests a file located in some drive W. The node can take the new stream only if there exists a new playback constant K( ) W  such that, like  in Architecture I, the two safey requirements are still satisfied, that is,  K^'RiU <Bi  i = l..n  T  dw  + l,  and  jr  Y ( L  K [ w )  Ri)  L(^)<KWVT,  < K U,  w = 1..MN,  {W)  t  w <> W.  i=i  4.2 Minimum Operation Set Past research [1] [2] has found the minimum safe operation set by finding the minimum playback constant with the two safety requirements satisfied. In this case, the server is busy almost throughout the service round either seeking or buffering data at the drive. In other words, the time to perform the operation set is  very close to the playback duration that each stream gets or the cycle time. This technique is not adequate when absorption of newly accepted streams  is to take place. As a new stream is accepted, the playback constant, thus the cycle time and the time to perform the new operation set, will increase. In the transition, starvation is likely to occur as insufficient data is available for the existing streams to play over the time to perform the new operation set. 27  Past research [3] added elasticity to the system by modifying the continuity criterion as follows:  I=  }2 L(ki) i=i  <  J2 (h L  + 1) <  i=i  . *  \ = *U =  \ 1  K x  r.  }  The above equation states that whether the server retrieves for stream i, ki or ki + 1 media blocks, the continuity criterion is not violated. The elasticity from this modification is shown in the following example. Say as a result of a new subscription, the operation for a particular stream changes from 6 to 10 media blocks. Because of the above modification, the server can  safely retrieve for that stream 7 media blocks a cycle instead of 6. Getting  a block of data in excess in every cycle, the client finds itself with 10 media blocks after 4 consecutive cycles. (In other words, the client's playback duration is increased until it becomes comparable with the new cycle time.)  After the  playback duration for all existing streams have been adjusted in the same way in parallel, the server can then absorb the new subscriber (or perform the new operation set) in the fifth cycle. This method has a few disadvantages.  First, this technique is well suited  for a unique case where all streams have the same playback rate. Second, in a transition only one new stream can be absorbed. Third, the transition can span through many cycles. 28  4.3 M  a  x  i  m  u  m O  p  e  r  a  t  i  o  n S  e  t  To make absorption of new streams elastic, we suggest finding the maximum safe operation set by finding the maximum playback constant n  max  which satisfies  the two safety requirements. The clients get the maximum playback duration that their buffers allow. In this scenario, if the system is not loaded, the server is busy for as long as it performs the operation set and is slack during the rest of the cycle time (See Figure 4.1). The slack time s is given by  S =  (4.1)  T - 1  This slack time makes the absorption process very elastic.  A newly accepted  stream is absorbed by placing its operation in the ordered operation set and performing the new operation set.  Data continuity is not impaired at existing  streams because double buffering is used.  Recall that with double buffering,  because each existing stream always plays back the load of data it received in the previous cycle, exactly when in a cycle the server performs the operations of the streams does not matter (See Figure 3.5).  29  buffer at stream 2  k U  !  2  i  1  R >R,  I  /  2  i i i i  t  buffer at stream 1 k,U  /  Ri Cycle time  t  1 time to perform operation set (busy period)  slack time  Figure 4.1 Absorption Elasticity due to Slack Time  4.4 F  i  n  d  i  n  g t  h  e M  a  x  i  m  u  m O  p  e  r  a  t  i  o  The following claims (with informal proof) help in finding the maximum playback constant. Claim  3.1  Increasing the playback constant, thus the operation set, increases the continuity criterion of the set.  Proof The extra playback duration each client get from an extra block is larger than 30  n S  e  t  the time the server retrieves that extra block. Thus when the playback constant increases, so does the slack time s . - i Claim  3.2  Increasing the playback constant, thus the operation set, decreases the feasibility criterion of the set.  Proof n increases, the quantity Bi — hU  i = l..n decreases.-i  To calculate the maximum playback constant, the following steps are taken: Find the maximum feasible operation set, or find K = n  max  \K Ri]U<Bi  i = l..n.  max  Then, check if with  K  =  K  M  A  X  such that  (4.2)  the set is continuous.  If it is not, there is no feasible-continuous operation set. From claim 3.2, if for  K — K  M  A  X  the set is not continuous, there is no feasible-continuous set  From claim 3.1, we can use the binary search concept to find  A c  m  a  i  .  We  start with a high K (corresponding to non-feasible set, say 1.0) and a low K (corresponding to feasible set, say 0.0).  The range (0.0, 1.0) is binary sliced  repeatedly until a given tolerance is reached. As a result of setting the low K to 0.0 with a sufficiently low tolerance, we are guaranteed that a feasible set will always be found. Then  K  M  A  X  is used to test if the set is continuous. The algorithm  is summarized in the flowchart given in Figure 4.2. 31  high K = 1.0  low K = 0.0 mid K = 0.5  tolerance = 0.00000000001  K = mid K  mid K = (high K + low K)/2  ( stop )  Figure 4.2 Calculating the Maximum Playback Constant 32  4.5 P  e  r  f  o  r  m  a  n  c  e  To analyze the performance of the architectures, we assume for simplicity that all streams are compressed video. Our aims are to investigate the relationships amongst the number of concurrent streams, the number of parallel drives and the client buffer size, to identify bottlenecks and to determine if the ATM switch can be used to the maximum.  Architecture I (striping)  If the number of parallel drives N is 1, the VME bus  and the ATM fibre link will not be utilized as long as the drive is seeking and buffering data at its DC. If N is increased, other drives in the array can use that idle time for data transfer. Increasing N in this fashion corresponds to a virtual increase in data retrieval rate and to increased utilization at the resources. We shall increase N until one of the resources, the VME bus or the ATM fibre link, saturates. The point at which saturation occurs will correspond to the maximum number of streams the node can support. Figure 4.3 shows the following. The number of concurrent streams increases with increasing client buffer size until a limit, caused by the speed of the drive arrangement, is reached. As N increases from 1 to 5, the virtual speed of the drive arrangement increases resulting in an increased number of concurrent streams. •  When N is 5, the node can support 79 concurrent streams. This maximum is reached because the ATM fibre link (at its designed bandwidth) saturates and 33  becomes the bottleneck. This means that the A T M switch, acting mainly as a concentrator for the five identical nodes, can be used to the maximum. A value of N greater than 5 does not increase the number of streams supportable.  34  Concurrent Streams 80.00  N= 6, 7, 8 N= 5  75.00 70.00  1 1 •  65.00  •  60.00  ^ ! '  55.00  i  50.00  1 1 1 1 , '  •  45.00 40.00  I  /'  N- ^  *  II  35.00  „  1 1 l (  30.00  N=2  ' ' -- 1 25.00 ll  If  1  20.00  II  1 ll Is II "  15.00 10.00  /f  5.00  1  • 1  *—  N= 1  I  •  0.00 300  3000 10000 Client Buffer (kB)  («)  Throughput 1.00 0.95  ,' ATM fibre I link  0.90 0.85 0.80 0.75  VM  0.70  I bus  ; r-" 1 /  0.65 0.60  ;/ ;/ :/ / /  0.55 0.50 0.45 0.40 0.35 0.30 0.25 0.20 0.15 0.10 0.05  ;/  / |  0.00 300  1000  3000 10000 Client Buffer (kB)  (b)  Figure 4.3 Performance of Architecture I  35  Architecture II (No striping)  In this architecture files are not striped among  drives. A l l drives operate independently. The speed of a drive is high enough to service a small set of streams.  Each drive competes for the buses and the  intermediates buffers.  When file requests are random, the same performance is obtained as with striping, that is a maximum of 79 video streams are supported, with the A T M fibre link reaching saturation. However, the maximum performance is obtained with a smaller buffer size at the clients. When all streams request the same file or files stored in the same drive, thus contending for the same drive, the performance is reduced considerably as only one drive is operating. The drive speed is so low that even though client buffer is increased, performance is not improved.  36  Concurrent Streams 80.00  lc+07 it Buffer  (a)  Throughput 10 A l M Rbre Li ik (Random ile Reques :  -*' f  E bus (Ranc om Hie Re {uests)  \f  1 1 11  1  I j  ATM Fibre -ink (Conh ndon)  s  ME bus (C >ntention)  lc+05  3  (b)  lc+06 Client Buffer  Figure 4.4 Performance of Architecture II 37  5 Design of New Admission Control: Architecture I 5.1 P  r  o  b  l  e  m  s o  fD  y  n  a  m  i  c P  l  a  y  b  a  c  k C  Recall that the maximum playback constant was previously calculated as follows: Find the maximum feasible operation set, or find  K RiU  < Bi  mas  K  M  A  =  K  M  A  X  such that  i = l..n.  Then, check with From above,  K  X  K =  K  M  A  X  if the operation set is continuous.  can be seen to depend on the buffer size available at each  and every client. Therefore, as the set of streams changes either because a new stream subscribes or because an old stream dies,  K  M  A  X  and thus the operations,  ,  also change. A changing First, when n  max  K  M  A  X  is highly undesirable because of the following two reasons.  changes, the server needs an adjustment phase. For example,  suppose a stream subscribes and is accepted, and then  K  M  A  X  increases. In general,  the server should not immediately absorb the new stream even though there exists plenty of slack time. In the adjustment phase, the server has to use the available slack time to adjust the playback duration of existing streams to the new cycle time. It is only after this adjustment that the server can absorb the new stream. 38  o  n  s  t  a  In the special case where slack time is large, the adjustment and the absorption can take place within a single cycle. Secondly, letting streams subscribe with a client-specified buffer size can reduce performance of the server. If a stream subscribes with a "stupidly" small buffer, the server may accept and absorb it but with the new n  max  Because  K  m  a  x  becoming small.  is small, the cycle time, thus the slack time, is also small. Because  the slack time is small, the critical stream constrains the server into accepting a small number of streams, even though the other streams have large buffers. Can we remove the dependence of the playback constant on the size of client buffers?  5 . 2 R a t e - b a s e d B u f f e r W e i g h t i n g  S c h e m e  QPMS suggested that the operation for a client should be proportional to its playback rate. It is natural then that the amount of data being buffered at the client might be also proportional to the client's playback rate. We, therefore, introduce the Rate-based Buffer Weighting Scheme RBWS (an accompaniment to QPMS) in which each client should subscribe with a buffer also proportional to its playback rate. Can such a buffer constraint on clients fix the playback constant? We make the following claim: Claim  If each stream subscribes such that 39  its operation is proportional to its playback rate (QPMS), that is, kj oc Rj, or more precisely, ki =  \KR{~\  its buffer is also proportional to its playback rate (RBWS), that is, BiocR,  or  Bi = RRi,  (5.1)  or more precisely, B,  U  U,  (5.2)  then, assuming the set is continuous, the playback constant does not change with the streams in the stream set. p is a proportionality constant which we call the  rate-based buffer weight constant. Proof To prove this, without loss of generality, let us drop the ceiling and floor functions. Given kj = KRJ and Bj — (3Rj, then the feasibility criterion leads to: kjU < Bj KRJU  i = l..n  < pRi  i = 1..71  P K<JJ  1 =  40  1..71.  (5.3)  We thus notice that if /? is fixed, the playback constant does not depend on the buffer size at the clients. the playback constant does not change with the number of subscribers in the stream set.—i To make absorption of streams elastic, we choose the playback constant to be maximum. Therefore, from (5.3), the maximum playback constant is given by  K  m  a  x  =  ^j.  (5.4)  5.3 C h o o s i n g t h e R a t e - b a s e d B u f f e r W e i g h t C o The rate-based buffer weight constant, along with the number of parallel drives among which files are striped, should be judicioulsy chosen such that the maximum number of streams accepted corresponds to the saturation of a resource in the node. In our case, it is the ATM fibre link that becomes the bottleneck. When the C S C A N disk scheduling policy is used and when all streams are video streams, the ATM fibre link nearly becomes saturated when the number of parallel drives N {N > 5, B  v  >  5 and the client buffer B  v  >  1 M B . The region  > 1 MB} is the region where the buffer-rate weight constant should  be picked. With a view to keeping the client buffers small we somewhat arbitrarily choose the point {N = 6,B  V  = I MB] to fix (5. At this point, if R denotes the playback v  41  rate of a video file, the rate-based buffer weight constant is given by  B  =  v  (5.5)  ftR , v  or more precisely, B  where B  v  5.4 M  a  = 1 MB and R  i  m  u  (5.6)  R'  U  V  = 175 kBps.  V  x  U_  v  ft  m O  p  e  r  a  t  i  o  n S  e  t S  i  z  e  «  The size of the operation set P is the total number of blocks that the o  server/node retrieves in a cycle for all the streams in the stream set. Thus, n  J>.  P =  (5.7)  i=l  The maximum size of the operation set p  m a x  is the maximum number of  blocks that the server retrieves in total for the stream set, where the maximum is due to the saturation of the A T M fibre link. At the point where ft was picked, the maximum number of video rate streams n  v  pmax  =  £  that the node can handle is 79. Thus,  .  k  i=l  = k{n , v  =  homogeneous set \K R ]n MAX  v  JJR  v  v  n,  from  v  42  (5.4)  B  v  I  U  TT}~R~: Rv  u  n,  from  v  (5.6)  B  v  JJ_ B  (5.8)  v  When all subscribers are video streams, the maximum operation set size is known. The quantity P  m a x  is therefore an important quantity as it is the basis for  a new way of designing the Admission Control. This quantity can now be used for predicting whether a node can accept a video stream or not. Basically, the node can accept a new video subscriber only if the new operation set size is less than or equal to P  m a x  . Is the importance of P  m a x  restricted to the homogeneous  case, where all subscribers are video streams? Is p  m a x  just as important for the  heterogeneous case, where subscribers can have any playback rate? We make the following claim: Claim  Provided the following conditions hold, namely,  the C S C A N disk scheduling policy is used, the chosen N is unchanged, the maximum playback constant is used, 43  •  the buffer-rate weight constant is fixed at the value chosen for the homogeneous case,  then, however heterogeneous the stream set is, the A T M fibre link is bound to saturate when the operation set size reaches the maximum operation set size.  Heuristic Proof The following two arguments give an intuitive proof of the claim:  •  Whatever the stream set is, the worst case model for the interfile seek, given by (3.5), is almost the same because the quantity JJ^(SM relative to SM and S . M  — S ) is very small M  This means that whatever the stream set is, the worst  case arrival pattern of media block sub-units from a row of drives at the A T M fibre link does not change much. •  Recapitulate that a row of drives are not utilizing the resources as long as  they seek they buffer data at the D C s .  Denote Tg as the total time that a row of drives spend on buffering data at the D C s in a cycle. A track of data takes one revolution time to be buffered at the D C . If r is the revolution time, then n  (5.9) i=l  44  The total time a row of drives spend on seeking in a cycle is given by (3.4). Adding Ts and TB gives n  T + T< S  B  M'(S  -S )  M  M  +  Y^ +Y  - S) M  +  T  /  ^  - S) M  .  J2  +  n  2J2-^(S  M  CM  " l)&n + r  -  S)  +  M  + rY i k  YiM  j=l  S) M  • +  O  + r  m  i=l  (const) + (const) ^]  fc^.  (5.10)  i=l  During this time T5 +  other identical rows of drives working in parallel  help to saturate the A T M fibre link during a cycle. Now, if the A T M fibre saturates for a particular homogeneous operation set whose size is equal to greater t h a n P  max  J>« i=l  n  k S  1=1  2(SM -  +  M  n  i—1  1=1 = M'(SM  -S )  M  i=l  n M  n  2  t'=l  = M'(5  i  n S  , then the A T M fibre will saturate for any heterogeneous  operation set whose size is equal to or greater than p  m a x  . The reason is that,  from (5.10), the bound on Ts + TB depends on the size of the operation set,  not on the size of a particular homogeneous stream  set.—i  The above claim is very useful for designing the Admission Control for Architecture I.  5.5 Admission Control Let the C S C A N policy be used. Let N, 45  K  m  a  x  ,  0,  and  P  max  be unchanged.  If a node is currently servicing n streams, then the node can accept and absorb a new stream j of playback rate Rj only if it subscribes with a buffer of size  [PR;  u and the new operation set size is less than or equal to P  m a x  , that is  n+l  (5.11)  In the simulation Figure 5.1, streams subscribe with different playback rates randomly between 10 kBps and 500kBps. The following points are noted: As the number of subscribers increases, the time to perform the operation set increases. Streams are accepted as long as this time is less than the cycle time. •  The proposed Admission Control can effectively predict whether the node can accept a new stream or not. At the point where the Admission Control rejects a subscriber, that is at the point where operation set size exceeds p  m a x  , the  time to perform the operation set also exceeds the cycle time. The point at which the Admission Control is about to reject a stream corresponds to saturation of the A T M fibre link. therefore efficient.  46  The Admission Control is  47  6 Design of New Admission Control: Architecture II 6 . 1 S t r e a m A d m i s s i o n In Architecture II, data is not striped among parallel disks.  The drives  operate independendy, each servicing a small set of streams and competing for the resources and intermediate buffers. Therefore a stream can be rejected because of two reasons.  First, one of the resources (in our case, the A T M fibre link)  saturates and becomes the bottleneck. Second, the speed of a drive under contention is so low that even though no resource saturates and even though client buffer is large, the drive cannot accommodate another stream. In this case, we shall say that the drive is limit  stressed.  6 . 2 C h o o s i n g  t h e R a t e - b a s e d B u f f e r W e i g h t  C o n s t a n t  Like Architecture I, Architecture II employs both QPMS and RBWS. The rate-based buffer weight constant should be wisely picked so that the maximum number of streams accepted corresponds to saturation of a resource, or in case of severe contention, to a drive being limit stressed. From Figures 4.3 and 4.4, the region {B > 0.5 MB} is a good region to v  pick /?. f3 should be as small as possible so that client buffers do not need be 48  large. We therefore pick the rate-based buffer weight constant as B  U_  V  (3 =  U _ R  V  where now B  = 0.5 MB  V  6.3 D  r  i  v  e M  a  x  and U = UT-  i  m  u  m O  p  e  r  a  t  i  o  n S  e  t S  Each drive services a small set of streams. The operation set size for a drive w servicing n i c  w  streams is the number of block units the server retrieves from  the drive, and is given by  d J>, n  w  P  r a  =  (6.1)  1=1  At the point where f3 was picked, the maximum number of video streams n i Vi(  r  a drive can support in case of severe contention is 15. This limit results  because the drive is limit stressed. The drive maximum operation set size p > max  is the maximum number of  dr  blocks that can be retrieved from a particular drive which is limit stressed. It is given by (5.8), modified slightly, as B  pmax,dr  V  n  v d r  .  (6.2)  This quantity is an important quantity as it can be used to predict how many video streams a drive can handle. Like before, we ask if this quantity is just as important in predicting whether or not a drive can take a stream of any playback 49  i  z  e  rate. We make the following claim, somewhat similar as before: Claim  Provided the following conditions hold, namely, 9  the C S C A N disk scheduling policy is used, the maximum playback constant is used, the rate-based buffer weight constant is fixed at the value chosen for the homogeneous case, then,  however heterogeneous the stream set for a drive is, that drive is bound  to become limit stressed when its operation set size reaches the drive maximum operation set size.  Heuristic Proof We give two arguments (similar to those in Section 5.4) to support the claim: •  Whatever the stream set for a drive, the worst case model for the interfile seek is almost the same.  •  If n i denotes the number of streams that drive j is servicing, the total time the ( j  drive spends on seeking and buffering data at the D C is given from (5.10) as  T  s  +T  B  < (S  M  - Sm) +  2(SM  —  CM  Sm) J  i=i  (6.3)  50  Again, because  Ts + TB depends on the operation set size for the drive, rather  than on the individual operations, the latter is bound to become limit stressed if its operation set size reaches p > max  irrespective of whether its stream set  dr 7  is homogeneous or heterogeneous.—i  6.4 M  a  x  i  m  u  m O  p  e  r  a  t  i  o  n S  e  t S  i  z  e  The stream set for the node is the union of the stream sets of the drives in the node. If the number of drives in the node is NM,  the size of the operation  set for the node is given by NM w=l NM  n  dw  = ££*>• w=lj=l 11  = 5>i  (6-4)  NM  where n =  £  n . dw  w=l  At the design point where j5 was picked, the maximum number of video streams n  v  the node can handle is 79. This limit is due to the saturation of the  A T M fibre link. The maximum operation set size given by (5.8), with proper modification, becomes  B  pmax  v  h. v  51  (6.5)  As before, we ask whether this quantity can be important in predicting admission of a stream of any playback rate. We make the following claim:  Claim Provided the following conditions hold, namely, the C S C A N disk scheduling policy is used, •  the maximum playback constant is used, the rate-based buffer weight constant is fixed at the value chosen for the homnogeneous case,  then,  however heterogeneous the stream sets are, the A T M fibre link is bound to  saturate when the operation set size for  the node reaches  p . max  Heuristic Proof Notice that since the SCSI bus rate is higher than the A T M fibre link rate, if a bottleneck is to occur, it would be due to the A T M fibre link. For both the homogeneous and heterogeneous cases, the rate-based buffer weight constant, and thus the cycle time, is the same. Therefore, for both cases, when the A T M fibre link is not saturated, the number of media blocks sent across it in a time slice of duration equal the cycle time is constant for a particular operation set size. This occurs even though the cycles for any drive are unsynchronized with those of the other drives in the node. As the operation set size increases until 52  p  max  is reached, the competition for  and queueing at the resources increases steadily, until the A T M fibre link reaches saturation. If for the homogeneous video-stream case the A T M fibre link saturates while handling p handling p  m a x  block units for a given cycle time, it should saturate while  block units for any heterogeneous case provided the cycle time is  m a x  of the same duration as for the homogeneous case.-n The above claims are important in the design of the Admission Control for Architecture II.  6.5 A  d  m  i  s  s  i  o  n C  Let the C S C A N policy be used. unchanged.  o  n  Let K , max  t  r  o  and P  (3, p > , max  l max  dr  Suppose a node is currently servicing n streams.  be  Suppose each  NM  drive w, w = 1..MN is servicing n  streams such that n = ^  dw  ng . Then the w  w=l  node can accept and absorb a new stream j requesting a file physically located in some drive W and having playback rate Rj, only if •  it subscribes with a buffer of size  the new operation set size for the drive is less than or equal to p > max  that is  dr 5  ki < p > , max  (6.6)  dr  i=l  the new operation set size for the node is less than or equal to p  m a x y  that is  n+1  J2k<P max  2=1  53  (6.7)  In the simulations of Figure 6.1 and 6.2, streams subscribes with playback rates between 10 kBps to 500 kBps. For Figure 6.1, streams request files in a random fashion whereas for Figure 6.2 streams contend for files located on a single drive. Streams are accepted as long as no starvation is detected. We notice the following:  The new Admission Control can effectively predict whether a new stream can be accepted. The number of streams accepted by the new Admission Control is very close to the number of streams derived form simulation with no starvation. For Figure 6.1, the point at which the new Admission Control rejects a stream corresponds to the saturation of the A T M fibre link. For Figure 6.2, the throughput at A T M fibre at the point at which the new Admission Control rejects a stream is very close to the A T M fibre link throughput at which rate-based buffer weight constant is picked. At this point the drive was said to be limit stressed.  54  Figure 6.1 Effectiveness of Admission Control (Random Files Requests)  55  56  7  Further  Discussions  7.1 Comparing Architectures Performance  Both architectures can maximize throughput at the A T M fibre  link and thus at the A T M switch.  Contention  In Architecture I, a node does not have a contention problem.  Because the node is servicing streams in bursts every cycle, whether the streams request a particular file or different files is irrelevant. If all streams contend for the same file (taking the worse case, with no phase difference among them), the drives of the node simply need to read the same data as many times as needed, provided the time to do so is less than the cycle time. Architecture II suffers from a contention problem.  If all streams request  the same file or files located on the same drive, they will contend for the same drive. Unfortunately, the drive cannot service any more concurrent streams after it becomes limit stressed.  Rate-based Buffer Weight Constant  Architecture II has a smaller rate-based  buffer weight constant than Architecture I. This means that smaller client buffers are required in Architecture II than in Architecture I. 57  Reliability  Architecture II is more reliable than Architecture I if no redundancy  and disk mirroring are assumed. In Architecture II, the probability that a file request is unachievable is in fact the probability that the drive in which the file is located fails. Let this probability that a drive fails be p. In Architecture I, the probability that a file request is unachievable is the probability that the disk-array in which the file is located fails. Due to striping, a whole disk-array fails if one or more drives in it fails. Probability a disk-array of N drives fails is thus 1 — (1 — p)  N  or approximately Np if N is large.  Obviously, p is smaller than 1 — (1 — p)  N  Np .  7.2 Admission Control Additional Features One possible criticism of our system is that rounding down operations results in reduced throughput of the server. To restore the throughput to its maximum, the new Admission Control should include the following additional features.  Staggered R o u n d i n g Technique  Past research [2] proposed a staggered round-  ing technique. In this technique two (or more) streams can be matched, that is two streams can share efficiently the space corresponding to 1 media block. For example, a stream whose unrounded operation is 4.2 can be matched with one whose unrounded operation is 6.8. The toggling for both streams can be easily synchronized such that when the operation for one of the streams is rounded up, 58  the operation for the other is rounded down. Therefore the two streams use a space of 11 blocks (("4.2 + 6.8]) instead of 12 blocks ([4.2] + [6.8]).  Dynamic Stream Set may be small.  For very small playback rates, the unrounded operation  For example, for an audio rate file (8 kBps), the unrounded  operation is 0.14. However, when the server rounds the operation up, the audio stream receives 1 block of data, but the audio stream needs only 0.14 block per cycle. The audio stream has so much excess data that the server indeed does not need to retrieve any data for it for the next 6 cycles. When the node accepts one audio stream, it could accept six other audio streams as well. The server can keep track of this fact and create a dynamic stream set. In this set, seven audio streams, in seven consecutive cycles, multiplex the space that one audio stream uses.  Non-Time-Critical Streams  Finally, not all media are time critical. The space  made free due to rounding down of operations could also be used by non-timecritical media such as text and still images.  7 . 3 Limitations Client Buffer Size  Our system uses the maximum operation set. One disadvan-  tage of this technique is that it requires large buffers at the clients even though the server has a light load. When lightiy loaded, the server that uses the minimum operation set can service the streams with smaller operations for the streams, 59  thus with smaller buffer size at the clients. Our counter-argument is that, with a minimum operation set, a stream subscribing with a small buffer may constrain the number of streams the server can admit. Allowing streams to subscribe with a client-specified buffer size plays counter to the objective of maximizing the number of streams.  Start-up Latency  The second disadvantage of our system is the start-up latency,  the time between a client receiving its data and its actual consumption of the data. When the maximum operation set is used, the cycle length is as large as possible. Obviously, because of double buffering, our system will have a larger start-up time as compared to one with a smaller cycle length. Our counter-argument is that, for the server that uses the minimum operation set, the cycle length increases when the stream set increases. As already pointed out, absorption of a stream (an incremental process in this case) may span over  several cycles. Moreover, newly  accepted streams are absorbed one at a time and have to wait for their turn to be absorbed. Therefore, while smaller start-up latency may be true when the stream set is small, it is not when the stream set is large. In our system, as many streams as the Admission Control accepts can be absorbed within the same cycle.  7.4 R  e  l  a  x  i  n  g t  h  e A  Linear-Seek-Time-Versus-Distance Model  s  s  u  m  p  t  i  o  n  s  In our study, a linear-seek-time-  versus-distance model is used. Our simple model, which uses the minimum seek 60  time and the maximum seek time given in the drive specifications, introduces a small error as can be seen in Figure 3.7.  However, we should point out that  while our study was developed for a linear seek-time-versus-distance model, it is not restricted to that particular one. As designers, we can arbitrarily choose the minimum and maximum seek times so that our linear model can be a worse-case bound on the measured seek-time-versus-distance curve.  Network Delays  In our study, all network delays were ignored.  Such an  assumption may sound restrictive, but turns out to be irrelevant if the same physical path/circuit (with a constant aggregate network delay) is established in every cycle between the server and a particular client . This network delay, if constant, simply delays by the same amount the arrival of all media blocks to a client and therefore does not impair the data continuity at the client.  61  8 R e l a t e d W o r k  8 . 1 S t o r a g e T e c h n i q u e s F o r D i g i t a l C o n t i n u o u s  M u l t i m e d i a  Rangan and Vin [7] address the problem of collocational storage of media strands, which are sequences of continuously recorded audio samples or video frames, on disks. They present a model that relates disk and device characteristics to the playback rates of media strands and derives storage patterns so as to guarantee continuous retrieval of media strands. To efficiently utilize the disk space, mechanisms for merging storage patterns of multiple strands are developed by filling the gaps between media blocks of one strand with the media blocks of the other strands. The merging process is briefly described as follows.  First, for one strand  (corresponding to a stream), the block size and the separation (gap) between successive blocks are determined based on the playback rate of the strand and the retrieval rate of the disk. Continuous retrieval can be guaranteed if the time to skip over a gap and retrieve another block does not exceed its playback duration. Merging a new strand is the procedure of storing the blocks of the latter in the gaps of the first strand. Several strands can be merged in this way.  62  8 . 2 D i s k  A r r a y s  A disk array [4] [8], which groups multiple drives into what appear to be a single logical volume, can narrow the gap between processors and hard disk by working the component drives in parallel. It uses data striping. Because the whole disk array fails if one or more drives fail, a disk array is less reliable than single drives. However, reliability of disk arrays can be increased using two techniques. In one technique, called Data Redundancy, the drives store some redundant data used to compute or predict the information data stored in any failed drive, very much like the error-correction bits used to recover information bits when a Hammingcoded data frame is corrupted by channel noise. The other technique is called Disk Mirroring, in which two drives store identical information.  If one drive  fails, its "mirror drive" serves as back-up. Both techniques involved huge data storage overhead.  8 . 3 S t r e a m i n g  R A I D  Tobagi, Pang, Baird and Gang [9] focus on the management of an array of disks. The disk arrangement is quite similar to ours. Several disks are connected to a bus to increase data throughput of the drive arrangement and a'microprocessor monitors the data retrieval. Data is striped among the disks. . 63  The data fetched is basically stored in the main memory, whereas in our system, data is stored at the clients themselves. to decrease buffering requirements.  They discuss two techniques  The first technique is sharing the buffers  among several streams. The streams do not really utilize all their required buffers throughout the whole cycle. When a stream has consumed the data from a buffer, it can release that buffer for use by another stream. The second technique is using subgrouping and subcycling. The streams are grouped in several groups. By properly time-offsetting the cycles for the groups, buffer occupancy can be reduced. They also discuss the issue of the start-up time. The start-up time for a stream depends on the start-up data stored, the scheduling strategy used and the number of streams in the system. subcycles.  To decrease start-up time, they employed separate  One subcycle involves performing the requests for active streams,  while the other for the newly arrived streams.  8.4 Caching Strategies Mechanical latencies are major causes of inefficiency in disk systems. Karedla, Spencer and Wherry [10] examine caching strategies to improve data throughput of disk systems. Three cache replacement algorithms are investigated, namely, random replacement, least recently used, and least frequently used. They may be implemented at the drive itself, the hosts' buffer or the main memory 64  of the system. Wherever they are implemented, they may reduce reads if some requests are for the same file and are close temporally. Even though those techniques virtually improve throughput of disk systems, they are ignored in our architectures. We should remember that in our system, the cause of the bottleneck is the ATM switch.  While the caching strategies  may relieve the work load at the drives, they do not do so at the ATM switch. Moreover, given the huge volume of data for a file, and its high playback rate, rarely will clients request the same file with minute phase difference among them. In other words, the principle of locality is not as pronounced in media data as in program data.  8.5 A  d  m  i  s  s  i  o  n C  o  n  t  r  o  l A  l  g  o  r  Vin and Rangan [11] consider two storage techniques. In contiguous allocation of media blocks, the media blocks are stored contiguously and thus successive blocks can be retrieved without incurring maximum seeks. However, contiguous allocation suffers from the problem of fragmentation which occurs during insertions and deletions. In unconstrained allocation of blocks on disk, blocks of data for a particular file are not stored contiguously but are somehow "scattered over" the drive. However, latencies are enormous as reading logically successive blocks involves several maximum seeks, the result being reduced throughput of the disk system. 65  i  t  h  m  s  They formulate Control Admission algorithms for both file storage techniques. However their algorithms include only characteristics of the drives and are therefore not close to being realistic.  8.6 S  t  a  t  i  s  t  i  c  a  l C  o  n  t  r  o  l A  d  m  i  s  Due to human perceptual tolerances and inherent redundancy in continuous media streams, most clients can tolerate a brief deterioration in playback continuity and occasional loss in media information. Worst-case assumptions that characterize deterministic control admissions constrain the server into admitting a small number of clients. Vin, Goyal, Goyal and Goyal [12] propose a statistical admission control. A new client can be accepted as long as the statistical estimation of the aggregate data rate requirement, rather than the peak rate requirement, is satisfied.  This  control admission may lead to violations in data continuity of some streams. To be statistically fair to all streams, they propose to distribute the violations among all existing streams within a pre-defined violation limit. Such an admission control, they found, can lead to a 200% increase in number of streams the server can support. Our server guarantees that it will retrieve data for the streams at their peak rates. No violations in data continuity can happen. 66  s  i  o  n  8.7 S  c  h  e  d  u  l  i  n  g P  o  l  i  c  i  e  s w  i  t  h B  a  t  c  ATM networks are equipped with a multicast facility. This feature can be used to reduce the number of streams required by the server to support a number of clients. Requests by multiple clients arriving within a short time interval can be batched together and serviced using a single stream [13].  For example, if  two clients request the same movie within a short interval, the server can delay the playback of the first client and service both requests using a single stream as opposed to two. Several policies are selected for multicasting namely: FCFS (First Come First Serve) Policy allows all requests to join a single queue. Requests for the same movie are satisfied by the same stream. MQL (Maximum Queue Length) Policy allows all requests for a specific movie to join a separate queue. The server starts a stream for the movie with the maximum number of requests. FCFS-n Policy allows requests for "hot" movies to be batched together in a single queue, and services those requests by starting a new stream after some batch interval. This batching technique is very useful and can be used in our server to increase the number of clients it can support, assuming that our switch has a multicasting feature. 67  h  i  n  g  8.8 S c h e d u l i n g P o l i c i e s f o r M u l t i m e d i a S e r Daigle and Strosnider [14] consider, a real-time scheduling approach to guarantee timing requirements for multimedia applications.  The scheduling model  services the requests in a round-robin fashion, but the order of service is not fixed for all cycles. Each request has a deadline before which it should be serviced, a priority depending on its media type, and a period within which another request must be made. They consider several scheduling policies, namely: In FCFS Policy, the request first on the queue is serviced first. In S C A N Policy, the requests are scanned and serviced according to their cylindrical location on the disks. In P-FCFS Policy, requests arrive at multiple queues, one for each media type or priority. P-SCAN Policy is similar to S C A N Policy, except that multiple queues, one for each media type, are scanned and their requests are serviced according to the priorities of the queues. However, in those scheduling policies, a large request may block a small request approaching its deadline.  Three techniques are discussed to reduce  blocking. The first one is using priority queues. A higher priority request may then virtually preempt a lower priority request. The second technique is chunking 68  a large request into smaller requests to be dispatched sequentially.  Chunking  allows chunk-level preemption. The third technique is transforming the period of all requests to a common period. This technique is basically the QPMS scheme.  8.9 L  a  n  c  a  s  t  e  r C  o  n  t  i  n  u  o  u  s M  e  d  i  a S  The LCMS server [15] and our server are similar in several ways, namely, round-robin servicing of streams, file striping, double buffering, availability of slack time. However, the two servers differ from each other in the following ways:  For our server, the data granularity was one track length and the operation for a stream is a multiple of it, depending on the playback rate of the stream (QPMS). For L C M S server, the data granularity depends on the playback rate of the stream, that is, the data block unit was proportional to the playback rate of the stream. However, in both servers the basic idea is the same, which is to retrieve more data for a higher-playback-rate file. Our server has a C S C A N disk scheduling policy.  The L C M S server has  a round-robin disk scheduling policy, servicing streams whose requests are closest to their deadlines. Wear is smaller in the former than in the latter. Our server chooses an optimum cycle length that guarantees that the maximum number of streams serviced corresponds to the maximum throughput at the 69  e  r  v  e  server. For the LCMS server, the choice of the cycle length is not discussed and the cycle length may not be optimum. Our server involves more architectural components than the L C M S server and is therefore more realistic. Moreover in spite of more architectural components, we developed a simple, effective and efficient Admission Control. Both servers noticed the problem of data accumulation at clients. In our server, this problem is solved by rounding down the operations and using a dynamic operation set. In the L C M S server, this problem is solved by skipping read requests for streams whose data accumulation has reached a certain limit.  8 . 1 0 M u t i m e d i a  S t o r a g e S e r v e r  ( M S S )  This server [16] is similar to our server in several techniques, namely, file striping, round-robin servicing of streams, S C A N disk scheduling policy, and double buffering. However, the two servers differ from each other in the following ways:  •  MSS has several secondary storage servers. Each secondary storage server stores a specific media type. For example, one of them stores M P E G files, while another one may store reduced quality video. Our server stores data of any media type. 70  For MSS, the Control Admission is designed for a specific media type or for a specific secondary storage server. The Control Admission for our server is flexible in that it predicts admission of a stream of any media type. The Control Admission for MSS was designed using disk parameters only and is therefore not realistic. The Control Admission we designed was for a fairly realistic system model. The MSS server has secondary (archival) storage system, while ours does not.  8 . 1 1 G o p h e r - s t y l e R e a l - t i m eA T M  M u l t i m e d i a S e r v i c e s  ( G R A M S )  GRAMS [17] and our server are similar in servicing streams in a round-robin fashion, but the order of service is not fixed for all cycles.  Both servers can  be configured for a distributed system. Both servers are designed for an A T M network. However, they are different in several ways, namely:  GRAMS considers only 3 media types, real-time media (video, audio), image and data. Our server deals with any media types. GRAMS uses real-time scheduling approach to guarantee timing requirements of real-time media. Our server uses C S C A N disk scheduling policy. Therefore wear is greater in the former. GRAMS scheduler prioritizes the media types. The server schedules real-time requests (video, audio) first and services them according to their deadlines. 71  The requests for other media types are serviced with lower priorities because they do not have time constraints. GRAMS admits streams as long it can satisfiy deadlines to some pre-defined deterioration limit. Our server has a Control Admission designed to guarantee data rate requirement of a stream once it is admitted. GRAMS implements Cache strategies to remove disk bottleneck, while our server does not.  72  9 C o n c l u s i o n s 9.1 Contributions We have presented two multimedia server architectures and a data retrieval model and have analyzed their performance in terms of the number of concurrent video streams that they can support using Circular S C A N disk scheduling policies. One of the architectures uses file striping while the other does not. For the analysis we have also developed a fast algorithm for finding the operation set. We have proposed finding the maximum operation set as a means of providing elasticity in the absorption of newly accepted streams. In this strategy, absorption of a stream takes place within a single cycle by using the server slack time. Moreover, several streams, whatever their playback rates, can be absorbed within a single cycle. We have introduced the Rate-based Buffer Weighting Scheme in which a stream subscribes with a buffer size proportional to its playback rate.  When  this scheme is applied along with QPMS, the operations do not change with new subscriptions or terminations. This scheme thus relieves the server from transitions that are necessary otherwise. We have also presented a new way of designing the Admission Control for both architectures.  The proposed Admission Control schemes are simple yet 73  effective and efficient. They are simple because predicting admission of a stream is a matter of comparing quantities. They are effective because they can predict admission of a new stream correctly and accurately. They are efficient because the maximum number of streams admitted by a node corresponds to the saturation of the ATM fibre link, and hence to the full utilization of the ATM switch. Finally, we have compared both architectures. Architecture II is more reliable and requires smaller buffer size at the clients. On the other hand, Architecture I does not present any contention problem. (While performance of Architecture II can be increased by having copies of "hot" files in different drives, duplication of files and copying of files from one disk to another result in waste of resources, namely memory space, bandwidth, and cpu time.)  9 . 2 C h o i c e  o f  A r c h i t e c t u r e  Choosing one architecture over another may depend not only on the merits and demerits of the individual architectures but also on the external factors. One external factor is the length of the files (in time). The shorter the file length, the less contention there exists, given a particular inter-subscription pattern of clients. Therefore, where the server is intended to service short clips, Architecture II might be the appropriate choice. On the other hand, if file length is long (for example a movie), contention for a hot file is highly probable, and duplication 74  of large files is obviously unwanted. For that type of application, Architecture I might be the choice.  9.3 Future Work We have focused on continuous servicing of streams of different playback rates. However, a multimedia object usually consists of more than one stream (audio and video as an example).  While maintaining continuity of individual  streams was one challenge, maintaining inter-media synchronization is another and is the subject of future work.  75  Bibliography  [1] D. P. Anderson, Y . Osawa, R. Govindan, "A File System for Continuous Media", A C M Transactions on Computer Sytems, Vol. 10, No. 4, November 1992, Pages 311-337. [2] P. V . Rangan, H. M . Vin, S. Ramanathan, "Designing an On-Demand Multemedia Service", IEEE Communications Magazine, July 1992. [3] P. V. Rangan, H . M . Vin, "Designing File Systems for Digital Video and Audio", Proc. 13th Symp. on Oper. Sys. Principles, Oper. Sys. Rev., vol. 25, no. 5, pp. 81-94, Oct. 1991. [4] C. Ruemmler, J. Wilkes, "An Introduction to Disk Drive Modeling", IEEE Computer, March 1994. [5] G . R. Ganger, B. L . Worthington, R. Y . Hou, Y . N. Patt, "Disk Arrays: High Performance, High-Reliability Storage Subsystems", IEEE Computer, March 1994. [6] A . L . N. Reddy, J. C. Wyllie, "I/O Issues in a Multimedia System", IEEE Computer, March 1994. [7] P. V. Rangan, H. M . Vin, "Efficient Storage Techniques for Digital Continuous Multimedia", IEEE Transactions on Knowledge and Data Engineering, vol. 5, no. 4, August 1993. [8] R. C. Alford, "Disk Arrays Explained", Byte, Oct. 1992. 76  [9] F. A. Tobagi, J. Pang, R. Baird, M . Gang, "Streaming RAID: A Disk Array Management System for Video Files", A C M Mutimedia, Aug 1993. [10] R. Karedla, J. Spencer, B. G. Wherry, "Caching Strategies to Improve Disk System Performance", IEEE Computer, March 1994. [11] H. M . Vin, P. V. Rangan, "Admission Control Algorithms for Multimedia On-Demand Servers" Proc. 13th Symp. on Oper. Sys. Principles, Oper. Sys. Rev., vol. 25, no. 5, Oct. 1991. [12] H . Vin, P. Goyal, A. Goyal, A. Goyal, "A Statistical Admission Control Algorithm for Multimedial Servers", A C M Mutimedia, Oct 1994. [13] A. Dan, D. Sitaram, P. Shahabuddin, "Scheduling Policies for an On-Demand Video Server with Batching", A C M Mutimedia, Oct 1994. [14] S. J. Daigle, J. K. Strosnider, "Disk Scheduling  for Multimedia Data  Streams", Proc. of the Conference on High-Speed Networking and Multimedia Computing by International Society for Optical Engineering, vol. 2188, pp. 212-223, Feb, 1994. [15] P. Lougher, D. Shepherd, "The Design and Implementation of a Continuous Media Storage Server", Proc. 13th Symp. on Oper. Sys. Principles, Oper. Sys. Rev., vol. 25, no. 5, pp. 81-94, Oct. 1991. [16] D. D. kandlur, M . Chen, Z. Shae, "Design of a Multimedia Storage Server", Proc. of the Conference on High-Speed Networking and Multimedia 77  Computing by International Society for Optical Engineering, vol. 2188, pp. 164-178, Feb, 1994. [17] J. Hui, J. Zhang, "GRAMS: A Distributed Multimedia Service System", Proc. of the Conference on High-Speed Networking and Multimedia Computing by International Society for Optical Engineering, vol. 2188, pp. 189-199, Feb, 1994. [18] J. D. Giacomo, Digital Bus Handbook, McGraw-Hill Inc, 1990. [19] American National Standard for Information  Systems, Serial Computer  System Interface, March 1990. [20] P. E. Livadas, File Structures : theory and practice, Prentice Hall, 1990. [21] M . J. Folk, B. Zoellick, File Structures, Addison-Wesley, 1992  78  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0064921/manifest

Comment

Related Items