\documentstyle[12pt]{report}

\setlength{\topmargin}{-.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.0in}
\renewcommand{\baselinestretch}{1.5}

\renewcommand{\thesection}{\arabic{section}}

\newcommand{\bgspc}{0.125in}
\begin{document}
\begin{titlepage}
\parbox{0in}{}
\vfill
\begin{center}
{\Large \bf A Case Study\\}
{\large \bf In Video E-Mail}
\end{center}
\vfill
\begin{flushright}
Brett Reid\\
6.033\\
Prof. Wing TR2\\
Case Study \#2
\end{flushright}
\vfill
\end{titlepage}
\end{document}


\section{Introduction}
	As technology grows, so do our means of communication.  As our means of communication grow, so does our technology.  One example of this is the proposed system to support video e-mail.  Technology has grown to the point where video e-mail may be introduced, but the current file systems will not completely accommodate the files of video e-mail.  The purpose of this case study is to show that two of the current systems cannot completely accommodate video e-mail and to give modifications to one of the file systems so it may work with video e-mail. 
\vspace{\bgspc}

\subsection{Unix Fast File System}

	One aspect of the Unix Fast File System that works particularly well with video e-mail is its cylinder groups.  Since files are rotationally optimal, it's easier for the Unix FFS to read the data faster.  
\vspace{\bgspc}

	The main problem with the Unix FFS is that the file system does not protect against fragmentation.  In the FFS, a file could become extremely fragmented.  If a video e-mail file was to become very fragmented, seek times could increase dramatically.  With increased seek times, the extra time could cause an application to be unable to display the file smoothly. 
\vspace{\bgspc}

	Another problem with the Unix FFS is that because the video e-mail files are so large, when one file is being transferred, the system cannot transfer anything else until the file has finished transferring.  This is not a major problem, but it can be an inconvenience.  The mean video e-mail file has a size of 72 megabytes, and the disk transfer rate is 4 to 8 megabytes per second.  So the file takes 12 to 24 seconds to transfer.  These numbers do not take into account the maximum transfer rate of the computer bus.   If the transfer rate of the bus is smaller than 4 megabytes per second, the transfer will take longer.  Twenty-four seconds is not a long time, but it is inconvenient and if other applications need to get something off the disk, those applications will be interrupted. 

\subsection{Sprite Log File System}

	Like the Fast File System, the Sprite Log File System, or Sprite LFS for short, can work with video e-mail although it also will have problems accommodating video e-mail.  
\vspace{\bgspc}

	Some aspects of the video e-mail that work sufficiently well with video e-mail are the reads and writes.  According to the paper on the LFS by Rosenblum and Ousterhout, the LFS can read 500 kilobytes per second from a disk with a maximum transfer rate of 1.3 megabytes per second.  This corresponds to approximately 38.5 percent of the disk bandwidth.  On the proposed systems, this is equivalent to a minimum transfer rate of 1.54 megabytes per second, which is sufficient for our purposes.  The performance of the writes does not matter because the data is not being viewed, and because the LFS writes sequentially for optimal reads. 
\vspace{\bgspc}

	The main problem with the Sprite LFS is that it assumes that most disk accesses will be writes, so that read requests are cached in main memory.  The problem is that because the video e-mail files are so large, they will flood the cache.  This is a problem because as the cache is flooded, data for the other applications will be replaced.  Therefore, read requests will be sent to the disk for those other applications.  This has the effect of slowing the data transfer rate to the video e-mail application and replacing the video e-mail data.  This in turn causes more read requests to be generated, causing the system to slow down further. 

\section{Overall Setup} 

	The system that I chose to modify to support video e-mail is the Sprite Log File System.  The primary modification that the LFS needs is a different caching strategy.  The LFS also needs larger block, fragment, and segment sizes.  Everything else should be kept the same because they work fine with the requirements for video e-mail.  This file system is called the Video Log File system, or VLFS for short and is designed to work by itself.

\section{Key Issues}

\subsection{Caching}

	A cache is a means of storage that can be gotten to quickly and can have data transferred into and out of quickly.  There are several strategies as to what data is put into the cache and replaced in the cache.  The most popular caching strategy is to replace the least recently used data.  This means that the data that the most time passed since its last access would be the data that is replaced when the cache is full.  

\subsection{Block, Fragment, and Segment Sizes}

	What are the b,f,s sizes? / intro

	The strategy for chosing the block and fragment size for a file system has two parts. One part depends on the sizes of the files that the file system would typically transfer and on how much space may be wasted.  The other part depends on the file system and the hardware system that the file system will be running on.
\vspace{\bgspc}

	There is a simple guideline for ideal block and fragment sizes: the block size should be the typical size of a file you will  transfer and the fragment size should be the size of the smallest file you will transfer.  The block size should be the size of a file that is typically transferred because for writes, there will not be fragmentation and much unused space left at the end of a block.  For reads, the block size should be the size of a file that the file system usually transfers because then most files can be transferred in a single disk access.  The fragment size should ideally be the size of the smallest file transferred in order to prevent wasting disk space.
\vspace{\bgspc}

	When one considers the file and hardware systems that the block and fragment sizes are for, the strategy for chosing the sizes becomes more complex.  It becomes more complex because one must now consider how the file and hardware systems can limit and increase sizes.  One way in which the file system affects the block and fragment sizes is in the way the file system writes and reads data.  For instance, in the proposed system, the disk has a maximum transfer rate of four to eight megabytes per second.  If the file is larger than the maximum transfer rate, then the block size cannot be any larger than that rate.  The file system and the hardware bus can limit the block size even further.
\vspace{\bgspc}

	The strategy for choosing the size of a segment is simpler than the strategy for choosing the block and fragment sizes.  It is simpler because one does not need to consider the transfer limitations of the file system.  Rosenblum and Ousterhout say, in their paper on the Sprite LFS, that the critical element is that the size of the segment is large enough so the transfer time is much greater than the cost of a seek to the beginning of a segment.  I do not think that this is the case.  I think that it also matters if the segment is large compared to the block size.  If the block size is larger than the segment size, then it is impossible to copy blocks into and out of a segment.  The paper uses a block size to segment size ratio of 1:250.  This is probably a good ratio to use.  

\section{Details of Changes} 

	There are two improvements I would make to the Sprite LFS.  The changes consist of developing a different caching strategy and increasing block, fragment, and segment sizes.

\subsection{Caching Strategy}

	The basic point of the VLFS's caching strategy is that because data can be read from the disk faster than the raw data rate necessary, 1.2 megabytes per second, a cache can be filled faster than an application can read the data.  This means that the application can always read data from a cache.  The VLFS avoids the problem of the LFS by allocation memory for an application for its own cache.
\vspace{\bgspc}

	The caching strategy for this file system is that the VLFS would grab about 10 megabytes of main memory for an application thread.  The file system grabs the memory for an application thread when the application requests the memory.  The 10 megabytes would be the least recently used of the main memory, and be used only for the application thread.  Or the file system would grab the 10 megabytes that would next be used by the cache if some other caching strategy is used by the system.  To replace information in the cache, the application flags data as the data is used.  If all of the data in the cache have not been read yet, then the VLFS stops the transfer until data can be put in the cache without writing over unused data.
\vspace{\bgspc}

	The application also requests the VLFS to deallocate the 10 megabytes.  

\subsection{Block, Fragment, and Segment Sizes}
	The other change to the system, the increase in block size would be to 1.5 megabytes.  The block size is increased to 1.5 megabytes because that is the rate at which the data may be read from the disk.  
\vspace{\bgspc}

	The ideal fragment size would be the frame size for a piece of video, 40 kilobytes.  Since this size is the smallest size that the VLFS would have to transfer, there would be almost no wastage of disk space.  However, a fragment must be one-half, one-fourth, or one-eighth of a block.  Since it is very important to have the maximum data transfer rate on a read, the fragment size should be 187500 bytes.  Again there is a problem, if that size is used then always either at least 27.5 kilobytes would be left unused, or 160 kilobytes could be left unused in a fragment.  Fortunately, this is not much of a problem.  The loss of 27.5 or 160 kilobytes does not matter much because they are very small compared to a 72 megabyte file.  
\vspace{\bgspc}

	The segment size should be increased to 375 megabytes.  Since the block size is 1.5 megabytes, 375 megabytes would keep the block size to fragment size ratio at 1:250 and the time to transfer 375 megabytes is certainly longer than the cost of a seek. Also, since the mean size for a video e-mail file is 72 megabytes 375 megabytes would contain a couple of files. 
 
\section{Performance}

	The test of any file system is its performance, especially for video e-mail, where a smooth display is the final test.  One indication that the VLFS will work as it is supposed to is that solves the primary problem of the LFS.  By limiting the VLFS cache to 10 megabytes, the file system prevents the other applications from generating many misses in the main cache.
\vspace{\bgspc}

	Since the ten megabytes stores approximately 10 seconds of video, moderate slowdowns in the disk transfer rate for less than 10 seconds will not affect the display rate and smoothness of the application.
\vspace{\bgspc}

	Unfortunately, the file system cannot support more than a couple of application threads at a time.  It cannot because if it did then there would not be any memory for the main cache.  If the VLFS cache is reduced, then more application threads can be supported, but then there will not be as much time for the disk to work on the requests of other applications.  Also, the file system will have to be rebuilt for the change in cache size to take effect.  
\vspace{\bgspc}

	Also on the negative side, allocating a relatively fixed amount of memory for the cache can waste some of the memory if the video message is smaller than the cache.  Also, the VLFS requires that the application is responsible for flagging bytes as they are read.  This makes the programming of an application more complex and therefore more prone to errors.
\vspace{\bgspc}

	The file system definitely would not support High Definition Television video e-mail.  A single 2000x1200x3 frame is has a size of 7.2 megabytes.  One second of video takes 518 megabytes.  Only a server subsystem has enough memory for a cache, and it would only hold about 2 seconds of data.  Also, to get a raw data stream of 518.4 megabytes per second, the disk used would need to have a maximum data rate of 1350 megabytes per second, far beyond today's technology.
 
\section{Conclusion} 

	The best argument for what I chose is in the previous section, but in some cases performance issues are not sufficient.  The arguments in the performance section can be insufficient in some cases because the parameters for the case could be changed without affecting performance.  One of these cases is why the cache size is 10 megabytes rather than some other number.  I picked 10 megabytes because it provides several seconds of memory, and did not take too long to fill as the video e-mail is being viewed.
\vspace{\bgspc}

	As this is just a case study and the file system may never be built, the final test can never be run but theoretically the file system should work.  
)F����y��w"��u���s����
q�
���o���"m1���k���hlo��y����w���su��s���q����o����m����k���@!ihl@!O!��2$yA$���$w�$���%u�%���(s�(��	*q*���+o�+��t,m�,��Q.k`.��hl`.�/y�/���1w�1���3u�3��}4s�(s�(��	*q*���+o�+��t,m�,��Q.k`.��hl������������������:��_��`����������������������������,��9��9@��S��`��h��y������������������������yyyy:y<yyy<y�y�y�y�
y�
y�
y�
y�y�y�y"y3y5y�y�y�y�y�y�y<��y�y�y�yqysy�y�y�y�yyy!y�y�y�y�y�y�y�y<��y�y�y�y�y�y�y@!yQ!yS!y2$yC$yE$y�$y�$y�$y�%y�%y�%y�(y<�(�(y�(y*y	*y *y"*y�+y�+y�+yt,y�,y�,yQ.yb.yd.y�/y�/y�/y�1y�1y<�1�1y�1���3���3w�3��}4��~4���+y�+yt,y�,y�,yQ.yb.yd.y�/y�/y�/y�1y�1y<<�
 %�0 too long to fill as the video e-mail is being viewed.
	As this is just a case study and the  (6/29/92 6/29/92 �3st can never be run but theoretically the file system should work.  
�����(�F�؀���JyS��"w+���u���(s�(��C0qL0���2o2 pt li�7�x�\^adhlo1�������������������:��_��`����������������������������,��9��
