Real CS 6235
Popular in Course
Popular in ComputerScienence
This 0 page Class Notes was uploaded by Alayna Veum on Monday November 2, 2015. The Class Notes belongs to CS 6235 at Georgia Institute of Technology - Main Campus taught by Calton Pu in Fall. Since its upload, it has received 18 views. For similar materials see /class/234066/cs-6235-georgia-institute-of-technology-main-campus in ComputerScienence at Georgia Institute of Technology - Main Campus.
Reviews for Real
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 11/02/15
CS4220 Embedded Systems 86235 RealTime Systems caltonpu cc TAs Jason Parekh 1 arekhcc Jinpeng Wei wei pcc Network o Realrate applications Q Realworld performance demands 0 Automated rate matching Q finegrain adjustment of allocation Q dynamic response to variable rates Q low programming complexity chedulers 0 Give CPU to highest prior 0 Scheduling policy oAssigns priorities to tasks 0 Scheduling mechanism oSort runnable task queue according to priorities oRun the task at the head ofthe queue 0 Example of problems oPriority inversion 0 Give tasks a proportional 0 Scheduling policy oAssign proportions to tasks 0 Scheduling mechanism oRoundrobin queue oTime slice allocated according to the proportion 0 Example of problems oNeed to cycle through queue fast o Prioritybased schedulers oaIIornothing or equal share c grained 0 unless aided by the application progra mer high complexity o Proportionalshare schedulers orequire program to specify resource nee s high compleXIty ohard to know forvariable rate apps lack dynamic response Allocation based on proportion and period progress inform ation Dynamic Allocator Feedback Scheduler Mechanism o Realrate task model oKnown CPU requirements oKnown deadline 0 Dynamic scheduler o Monitors task progress towards deadli e olnsufficient CPU increase allocation oDo it fast enough before miss 0 Application progress monitor 0 Resource resenation scheduler 0 Dynamic allocator 9 Feedback based allocator samples progress 9 Calculates resource needs assigns allocation Progrea stimation 0 Automated monitoring fea 39 oSymbiotic interfaces between application 0 Concrete examples oServer consumer of a bounded buffe o Data rate of shared memory queues sockets pipes etc o lO intensive consumers ofthe lO subsystem o Interactive listen to tty instead of sockets Producer l D Assign Allocation to Monitor Progress Produc er Consumer Feedback Scheduler Progr Monitor Inc om ing queue Fa IZIZIIZD Pressure Fa Fb 0 Fill levels show data flow pressure 9 High pressure increase CPU allocationpriority 9 Low pressure decrease allocationpriority 9 Goal keep data owing smoothly o Realrate pressure fed to PID controller 0 Realtime progress towards resenation fed to PID controller 0 Other constant positive pressure bypass adaptation Pre ssure Overload cation Policy 0 Realtime orenegotiate resenations admi 0 Others oweighted fair sharing proportional squishing oTransient load jobs regain allocation oLongterm load quality exceptions to applications 0 Applications can shed load 0 Increase job importance o Reservation scheduler obased on proportion and perio ouses ratemonotonic scheduling oallocations enforced during process dispatch oallows fine granularity allocation adjustmen olow overhead for changing resenations o respects reservations for applications that specify them Allocato Response Producer Variable CD a production rate consumption rate Fixed Allocation allocation Response 0 Response to varying progress 0 Vary the progress rate of the producer 9 fixed allocation variable production rate 0 Measure the progress rate of the consumer 9 variable allocation fixed consumption rate 0 Progress rate allocation X productionconsumption rate Results 0 Allocator response 9 adjusts consumer s allocation rapidly 9 matches producer s progress rate Results 0 oaded System 0 The other load does not have a progress metric o Other load loses allocation to the realrate consumer job Alloca Overhead um m a 5 um um l lt m l 3 y m a m nmhcr u L umrullnd PI mm 0 Linear with number of threads under our control 0 Small slope of prototype 006 per process Benefits 0 ur Approach 0 Finer grained allocation 0 Avoids starvation and priority 39 0 Easy admission control 0 Automatic estimation of reservation 0 Implementation in Linux source code available at httpWWW cse ogi eduDS Cprojectsquas reeases Re 0 Realtime priorities 0 Proportional allocation Walds o Reservation Schedulers Nieh J Previous work focuses on satisfying requirements rather than Inferring reqUIrements accurately o Balancing between realtime and normal jobs 0 Pipeline based allocation Jeffay CS4220 Embedded Systems Jinpeng Wei wei39pcc Predictability 0 A representative workloa e Sufficient coverage and resourc 7 Easy to understand 0 Compare the alternative target syste s 7 Show the execution time and variances e Vary the environment in a controlled mann e Sufficient coverage and consistency 0 Visual representation of 1 0 Typical XY graphs 7 Show a relationship or statistical c 7 Best when it s one variable and clear r ation 0 Other graphs 7 Visual impact in this paper 7 Multiple relationships dif cult to do 0 Eg HertzsprungRussell HR diagram 39 X Server nonRT 60000 usec 10000 o Situation Linux c ot handle realtime appli o Hypothesis a few techniques can v the limitations of Linux 7 Firm timer high resolution 7 Finegrain kernel preemption 7 Priority and reservationbased scheduling 0 Good performance and low overhead Even dling Structure Timer Latency mampuun Lavenc p ling Latency 1 mm W Annrleynppll on manual relort unw Wall emu mm lulurmpl summer Awhrnrmn whemrk d lannaimal 0 Scientific analysis ofthe problem 0 Engineering solutions for each component and Solutions o Firm Timer reduces tI 7 Low overhead important r latency o Finegrain kernel preemption red e preemption latency 7 Responsive kernel 0 Good schedulers reduce scheduling late y 7 Proportionperiod scheduler 39 X Server nonRT contention nization 40000 39 39 usec I 1 quot r I 39Iquot r r 39 F 1 39I I 10000 F quot Ill I I 0 I and Solutions o Firm Timer reduces timer tency 7 Low overhead important 0 Finegrain kernel preemptio reduces preemption latency 7 Responsive kernel 0 Good schedulers reduce scheduling late y 7 Proportionperiod scheduler Linux ke CPU contention psec 10000 TSL ke CPU contention 400 psec Wm contention 120000 I39 I quot39 psec 391 I quotH i 41 i quot h l I ht 10000 31 a quot 1 rhi 0 Mi TSL fi e stem contention 500 psec and Solutions o Firm Timer reduces timer tency 7 Low overhead important 0 Finegrain kernel preemption red e preemption latency 7 Responsive kernel 0 Good schedulers reduce scheduli g latency 7 Proportionperiod scheduler 8000 I psec I III 539 DD I 5391 11139 3 l39I39 IIIY 5 60000 IIZIJ psec 393 LinuxSR 39 system contention 30000 I psec 539 Timers 0 Periodic timer in Linux 7 Tradeoff between latency and 0 Oneshot timers 7 Reprogrammed for next timer interrup 0 Soft timers reduce interrupt overhead 7 Polling at convenient times e g syscall ret rn o Timer overshoot 7 Reduce variance due to soft timer uncertainty 7 Only disable interrupts when accessin hare data structures protected by spin locks 7 Voluntarily check for interrupts when long sections of code being locked eriod Scheduler Proportl 0 For each period a propo 39 of CPU is allocated 7 A periodic scheduler proportional 7 Highest locking priority HLP protoc 7 Bounded execution time for shared code inherited high priority Overh of Firm Timers 17G39l ipquot39i39lill 239 M nu 51quotin Iimm I1 I 1915 a l 39I Im 1 lt E l I quot1 I Hm MAI linnu IIanFxirml mrm w MI CS4220 Embedded Systems 235 RealTime Systems caltonpu cc TAs Jason Parekh j arekhcc Jinpeng Wei weij cc Application Presentation Session software Transport Network Logical Link Control Data Link Media Access Control Physical board Trans sion Time Sender Receiver Cost Above Cost Above i Cost of Cost of Interest Interest MAC MAC 1 l Cost Below H Propagation H Cost Below Classification Synchronous messages 7 Periodic predictable stream se 7 Arrival time job creation 7 Length job resource requirement 7 Deadline job completion requirement 0 Asynchronous messages 7 Aperiodic task communications alerts 7 Unpredictable arrivals length deadline Arbitration 0 Network as a shared reso 7 Rate monotonic scheduling of b 0 Desirable properties 7 Bandwidth utilization for synchronou 7 Robustness not brittle 7 Timing fault isolation and limitation 7 Accommodate asynchronous messages 7 Low runtime overhead tonic Scheduler 0 Classic hard realtime C 0 Decides who gets the resource 7 CPU in the original work 7 Network bandwidth in MAC 0 Static scheduler fixed priorities 7 No dynamic priority adjustments 7 Not a static schedule o Assumptions oJobs are periodic marked by s oJobs are independent 0 Shorter period jobs get higher prio 39ty I CE I39l I Time line o Synchronous messages oArrival length deadline Time line o Simulate preemption oDivide message into packets sohedang I EEI I I Time line 0 Evaluation criteria 7 Bandwidth utilization guarante limit of 0693 for CPU 7 Robustness OK if below the 0693 1i 7 Timing fault limited by preemption 7 Asynchronous messages high priority unti the 0693 limit 7 Runtime overhead may be high fig 4 Priorl riven Protocol A age mm mm mgr mu ape ma v mph4mm mg 13mm I I w mm mm Bamme Mm s 0 Timed token protocol 7 Nodes are arranged in a ring 7 Each node receives the token in se 7 Node k transmits Hk packets prede n 7 Token rotation time bounded half of mi 39mum deadline 7 If token arrives early send asynchronous messages ling Analog 0 Timed token protocol 7 Token rotation time bounded to guarant equivalent of preemption 7 If token arrives early send asynchronous messages different priorities of Timed Token 0 Evaluation criteria 7 Bandwidth utilization 033 W 7 Robustness OK if below the 033 l Shortest Path and 045 heuristic 7 Timing fault limited by H k time slice 7 Asynchronous messages squeezed in 7 Low runtime overhead good scalability fi 5 Time ken Protocol ux iuomum mo mems lu39mccu muons M P1 in m Signal mom a mu 5v munm u iglvn I I it lol mm mm Bandwidth lVliVlls sW ous Messages 0 Unpredictable arrivals o Guarantees in dynamic sched 7 Periodic server reserved bandwid a synchronous messages 7 Conservative estimation Worst case an of all messages underutilization 7 Dynamic reservations control message to reserve future bandwidth overhead rt Scheduling 0 Minimum laxity first M 7 LaXity time to latest feasible the job can still complete 7 Run the job closest to failing first 7 Optimal in minimizing deadline failures 7 EarliestDeadline First EDF also optimal 7 MLF EDF when jobs have same length 7 deadlinedriven scheduling 0 Some drawbacks when priorityb e 7 Overhead in priority arbitration 7 MLF requires dynamic reprioritization 7 Priority inversion due to insufficient numb of priority levels 7 Asynchronous messages aperiodic 39 b 0 Scheduling strategies 7 Access arbitration who gets to use the re urce network bandwidth or CPU 7 Transmission control how long one gets to the resource bandwidth 7 Shorter period gets higher prior 7 Tight worst case achievable utilizat39 n 0 Minimum laxity first for aperiodic j 7 Closer to failure gets higher priority 7 Optimal in minimization of failures 7 Related to EDF Analythal Graph u 0 u my lukcu pmsmg lgt hm V Pumm m m um R W WM nu mu uuw n no 39 u mm l mu 3 my 21 Scheduling algorithms fa1 o Prevent overload 7 Static schedules 7 Admission control 0 Overload management 7 Congestion control 7 Adaptive QoS driven resource managemen ion Control 0 Asynchronous messages 7 Guaranteed dynamically 7 Conservative estimation worstcas all messages in a node 7 Main problem underutilization 0 How to sharpen the estimation and incr network utilization 0 Network model 7 Diffserv architecture with clas Resource management componen 7 Con guration class amp route determin tion 7 Runtime admission control enforce admission policies when under overload 7 Packet forwarding classbased static priori policy FIFO within class 7 Current utilization the only criterio 0 Bandwidth availability along ow p h 7 Safe levels of utilization 7 Determined during configuration 7 Traf c constraint bounds usage 7 Server delay bound 7 lterate the delay calculation on all se 0 Safe route selection 7 Satisfy deadlines of each class and route 7 Heuristics min distance min delay e Utilization 0 MaX utilization bounds de nd on network diameter theorem 4 7 Given a utilization level find safe 7 Converge on max utilization that has s e routes 0 Their result 45 is better than Shortes Path 33 CS4220 Embedded Systems S6235 RealTime Systems 6A Rate otonic Scheduler Instructor caltonpu cc TAs Jason Parekh j arekhcc Jinpeng Wei weiJ cc tonic Scheduler 0 Classic hard realtime C e Preemptionbased 7 Independent tasks 0 Static scheduler fixed priorities 7 No dynamic priority adjustments 7 Not a static schedule 0 Main components 7 Periodic tasks marked by start 7 Prioritybased preemption 7 Shorter period tasks get higher priorit I I39l I Time line 0 Only need to check the rst 7 If tasks make their first deadline make the following deadlines II III III E EDl llll Time line 0 Zhao s evaluation criteria 7 CPU utilization guaranteed the limit of 0693 for CPU 7 Robustness OK if below the 0693 1i 7 Timing fault limited by preemption 7 Aperiodic jobs high priority until the 069 WCAU limit 7 Runtime overhead may be high Discussion 0 Sha s list of advantages 7 Fixed priorities easy managem 7 Aperiodic tasks sporadic server et 7 Synchronization priority ceiling etc 7 lmprecise computations 7 Ease of implementation 7 Worst case may be too stringen 7 Guarantee a set of critical tasks for case WCAU 7 Add other tasks at lower priorities 0 During overload 7 Set of highest priority tasks run normally continue to be guaranteed 0 A period transformation task 7 DiVide the task into k pieces 7 Run each piece in its own period size k 7 Original task completed with the last piec 0 Complications and issues 7 Context switch overhead k times 7 Portability synchronization 0 Two kinds of aperiodic ta 7 High priority emergency alerts 7 Low priority background jobs 0 Problem with background jobs 7 Neglected during transient overload 7 Long response time example 3 p 56 High 0 Aperiodic server 7 Subschedules its allotted time slic 7 Can preempt normal periodic tasks 0 Constraints and issues 7 Preallocation counts towards WCAU limit 7 Independent replenishment and overload handling policies Chronization 0 Priority inversion examp 4 p 57 7 Priorities combined with lockin 7 T3 holding lockA is preempted b needs lockA 7 T1 waits for T3 and T3 waits for T2 0 Examples of remedies 7 No preemption when holding lockA also introduces priority inversion 0 Priority inheritance 7 Ile waits for T3 then T3 gets 0 Dynamic rescheduling 7 Critical sections execute at highest prio ity 7 Waiting is outside critical sections 7 Highest priority waiting task runs next 7 Critical section becomes a subroutine of the highest priority waiting task 0 Deadlock free example 7 Critical section always runs 7 Waiting is outside critical sections 7 T2 prevents Tl from getting lock fig 0 Bounded priority inversion 7 High priority tasks jump over queues 0 Good schedulability tests Furthe 39 cussion of PC 0 Priority inversion 7 Low priority tasks in critical se 39 high priority 7 Tasks wo critical sections may wait 0 Execution overhead 7 Every critical section needs a priority queu rt Scheduling 0 Minimum laxity first M 7 LaXity time to latest feasible the job can still complete 7 Run the job closest to failing first 7 Optimal in minimizing deadline failures 7 EarliestDeadline First EDF also optimal 7 MLF EDF when jobs have same length 7 Predictable program properties 7 Realtime a big application target 7 One way to do each task 0 Some dif culties with realtime 7 Nondeterministic task scheduling 7 Prioritized tasks queued in FIFO order 7 No dynamic change of task priorities CS4220 Embedded Systems oS m portant 7 Multimedia presentation r irements exceed available resource capacity 0 presentation requirements are increa 39 0 range of resource capabilities is widenin 7 In general resource saturation 0 Transient sudden demand 0 Natural evolution of steady state load 0 Denial of service attacks network will set up a reservation an guarantee 0 QoS requirements derived from stored representation of encoded media 7 It s a systems issue not a rich area for database semantics research 7 Involves all resources 0 CPU memory disk IO networ 7 In general you won t get guarante o mobility wireless networks o increasingly heterogeneous hardware and s tware o increasingly high quality stored data 7 QoS about specifying adaptation policies 0 A much richer space for QoS semantics Poss39 Approaches 7 Make users deal with the c underlying system 0 doesn t scale 7 Let systems decide what data to drop 0 not enough information available 0 no single solution many different usersuses the same media data Models 7 Goals 0 ability to trade sensibly between entation quality and resource consumption requirem t o ability to trade sensibly between differe t as presentation quality 0 independence among Viewing requirements characteristics of the physical environment 0 independence among authoring and Viewing decisions 0 used to derive systemlevel adap 7 Author quality preferences 0 default quality or adaptation policy for c of complex presentations 7 Quality inherent in stored representations 0 maximum feasible presentation quality 0 resource consumption characteristics and adaptat options Compone of Quasar Model 7 Content specification 0 author describes complex conten ing an editor 7 View specification 0 user maps logical coordinates of content world coordinates using player controls 0 defines ideal for this user presentation 7 Quality specification 0 user defines importance of different kinds of erro s wrt the ideal presentation using player controls Utility IOSSmin lOSSmax Quality Loss gt 7 There are many different s to affect the quality of a presentation 7 Quality dimensions expose orthog a omain specific quality adaptations 7 Real systems export quality dimension or controlling quality in a few predefined wa s For a Video Streamin Color depth bits per pixel Vertical I resolution pixels i Horizontal resolution pixels Quality Dimension 1 Exposing ality Dimensions 7 SPEG Video format derive 0 groups data for different quality 39 separate data units 0 units can be transmitted and processed independently o dropping a unit reduces quality in that dimen ion only M PEG SPEG Low resolution I High frame rate High resolution I I a Low frame rate 7 Multidimensional utility faces are too complex to be practical o a simple utility function per dimensi 0 weighted combination of utility functio approximates the surface 0 users typically select from a few prespecifie functions Qo 7 Small domainspecific lan specification of 39crolanguage ge for declarative 0 quality dimensions 0 utility functions one per dimension 0 lossmin and lossmax thresholds 0 weighted combination of utility functions 0 QoS exception handlers ation Mechanism Quality 7 DataDropping Virtual Ma 0 interprets QoS microprograms a to data units signs priorities 0 priority assignment xes an adaptation olic 0 data dropped later in priority order if nec sary 0 data dropping priority threshold controlled V1 feedbackbased resource managers 0 adaptation policy can be changed dynamically Npthrki Identify content Client Dynamic Qo daptation 2 Index amp Data Fetch data Priority Labeling Server 1 Network Specification Client Dynamic Qo Index amp Data Data Priority Labeling Server Fetch data daptation 3 Network Low priority amp transcoding Client data dropped 7 Adaptation policy determined dyn user Via utility functions 7 Adaptation implemented using simple mechanisms anywhere in the system Other ar Components 7 SWiFT a toolkit for buil 39 feedbackbased controllers 7 Feedbackbased adaptive resource 0 CPU Realrate scheduler for Linux 0 Network SCP streamingcongestion contro protocol and PMI dynamic interface switchin 0 Storage synthetic les amp adaptive prefetcher f Linux 7 Applications streaming Videoaudio players ity Dimensions 0 Endtoend Quality of Se 7 Timeliness response time 7 Scalability throughput 7 Reliability and availability 7 Security confidentiality and integrity 7 Survivability failures are inevitable 7 Resistance to denial of service 7 etc 0 Information analog of Q0 7 Timeliness fresh information 7 Completeness e g no answer 7 Consistency among replicas and cache 7 Consistency among independent sources 7 Reliability and trustworthiness 7 etc CS4220 Embedded Systems Jinpeng Wei we139pcc 0 What was Ubiquitous Co uting in 1993 0 Phases of Development 0 A New Form of Computer Scienc 0 Hardware Issues 0 Applications 0 Where are We Now 0 Very new to the eld of 7 Ubiquitous Computing was int Weiser in 1991 0 Main goal was and still is to get t computers out of the way of everyd activities 0 Technology finally caught up to the proposed ideas for environmental computing was the ideal ology was 0 Some thought Virtual Re UbiComp solution but the te not advanced enough 0 Ruled out GUls as the complete so tio 0 Identi ed several key needs of a succ sful UbiComp device 0 Still struggling with some of the same problems today 7 Construct 7 Deploy 7 Evaluate 0 Realized that Phase One would not achi ve the optimal invisibility Platforms 0 Devices of various sizes 0 Enough diversity to give some scope 0 Must be found in everyday life and frequently 0 Above all they must be unobtrusive Larg 39ze Prototype O LiveBoard Look to the 39 0 Main idea was to simulate an Whiteboard 0 Order of l per of ce 37 A Mediu ize Prototype o XPad 0 Main goal was to simulate notebook 0 Order of 10 per person Sma 39ze Prototype o ParcTab 0 Main goal was to simulate Pos 0 Order of 100 per person o Valuable lessons learned from th prototypes 0 Development of a new hierarchical abs actio specific to UbiComp framework 0 Main goal of this paper is to discuss the motivations behind this new form of CS and the current obstacles hical Abstraction Hardware D Network Protocols 3 Interaction Substrates 3 Applications Hardw Requirements 0 Low Power 7 Speed can be sacrificed 0 Wireless 7 One lowspeed 64kbps per person 7 Remember this is 1993 0 Pens 7 Wireless IR beams 7 Available without touching the screen and up 0 several feet away 0 A media access protocol is req 0 Some applications require guarante bandwidth voice and video 0 Example MACA Karn 90 7 Uses a handshake algorithm that verifies communication channel and lets others know f upcoming transmission o RealTime Protocols 7 Focus on packetswitched net 7 Attempt to eliminate bottlenecks a a stations 7 Work in progress at the time no conc te details are provided 0 Secondary or Virtual 1P 7 Adds a level of indirection to account for us r mobility Intera 0 IR Pens o No look touch screens 0 Palm size keyboard 7 Found to be only half as fast 0 Window migration tools 0 Low Bandwidth X Fulton 93 Ea 0 Active Badge 7 An employee tracker 7 ATampT Labs in Cambridge 0 Slate 7 Shared media tool 7 Xerox PARC 0 Both Widely used even outside of the labs 0 UbiComp has unveiled se theoretical problems that nee For example 7 Optimal Cache Sharing Problem 0 Optimal strategy for partitioning memory be ween compressed and uncompressed pages 0 Led to the development of the Lower Bound Theorem for Caches Bern 93 0 Still developing new tech 0 Have met the demands for 7 Wireless Networking IEEE 80211 7 Low Power CPUs 300 MHZ at 11v 7 RealTime Packet Switching Numerous algorithms 7 Applications Entire OSs have been built Remote erlment Control NEE it i swammmirecme i m g quot390 11 2 559 1 T 7 7 Equipmemsne NEESgnd m can E i in um i 7 SDSC El 7 4 r v Remme Callubarmor 39 Environ tal Forecasting 0 Columbia River monitoring and forecasting TrendSoft ProAnalyst IhttpwwwtrendsoftcomProAnalystmain htm o Ha102 multi layer httpwwwxboxco me n ushaloZdefaulthtm 0 nl I n 39 0 Radio TV Video 0 Virtual reality Create your own custnmlzed LAUNCHcast radlu siallnn ks he mpmwm quotarmor 9 WM Hum 5quotan qulskzr i DuKkEntry 1 Wherify39s Online Store Wherify Store Weicume m Whemv s unhne 5mm On Our Site Omevmg vuuv GPS Lucamv is as easy 1473 average Map 5 ENNIS hel n Pickme cuimyuu wam Fm detaHed pvuducl mmmannn swam Check em an my in make suve mm 5 sevwce mme desned avea mum 9 mesm mm Please allow 4 r 6 Weeks my dervery n m have am we hans Vee nee in ca am Cusmmev Cave hne m anvwswv museums We H he happv a heip m CS4220 Embedded Systems 86235 RealTime Systems Jinpeng Wei we 39pcc Network o Realrate applications Q Realworld performance demands 0 Automated rate matching Q finegrain adjustment of allocation Q dynamic response to variable rates Q low programming complexity Feed ba Approach Applicationspecific Allocation based on progress ED Threads proportion information and period Dynamic Allocator Feedback Scheduler S cheduling Mechanism o Realrate task model oKnown CPU requirements oKnown deadline 0 Dynamic scheduler o Monitors task progress towards deadli olnsufficient CPU increase allocation oDo it fast enough before miss Symbiotic Interfaces 0 Application progress monitor 0 Resource reservation scheduler 0 Dynamic allocator 9 Feedback based allocator samples progress 9 Calculates resource needs assigns allocation 0 Automated monitoring fea 39 oSymbiotic interfaces between s application 0 Concrete examples oServer consumer of a bounded buffer oData rate of shared memory queues sockets pipes etc olO intensive consumers of the lO subsystem 9 Interactive listen to tty instead of sockets Queu xample Producer l D Assign Allocation to Monitor Progress Produc er Consumer Feedback Scheduler Progr Monitor coming Inqueue Fa Fb eue IIIII Oulgoing Pressure Fa Fb 0 Fill levels show data flow pressure Q High pressure increase CPU allocationpriority Q Low pressure decrease allocationpriority Q Goal keep data flowing smoothly o RealRate applications 9 IP telephony o Videoconferencing 9 Remote sensors over network 0 Common aspects 9 Delaysensitive data must be delivered from senderto receiver in bounded time o Selfratereguated eg live video source from camera break our infinite source assumption plications in the Sender Si dc Receiver Side Data Data Encoding I Sender of Congestion Control Receiver of Congestion Control Realrate o Buffering delay between realrate ap icati amp congestion control protocol 9 It is caused by rate mismatches lnput rate is controlled by the application adaptation Output rate is controlled by the congestion control 0 TCPfriendly congestion control TCP with e Source Rate Rate In nite source Limited source Input buffer empty now Average x 7 l l l l Output Limit Input Rate Time Time 0 Infinite sources Finite sources t TCP expands its window at I TCP is in full speedquot hen full speed input buffer has data Less aggressive when in ut buffer is empty Average TCP C Throu h Lit g P RTT39 5 Can t model TCP independ ntLy Rate If Input Rate is Average Outfut Input Output her Than Output 0 Buffer Filllevel B es a A Buffering Data 0 Solution Application Adaptations Time 39on Based on Local Congestion 1 Control Protocol Rate 3 Output L39 it Output Limit Input o Adaptation Reducingl put rate to be less than the average of output 0 System goes to the finite source case Manages outgoing network interface bandwidth Buffers amp multiplexes different streams Determines inter packet intervals and overall bandwidt allocation for each stream Conventional EndHost OS uses FCFS policy o Unpredictable delays 9 Many FTP packets may be inserted between consecutive video packets o FCFS scheduling does not guarantee service intervals Competition for bandwidth Besteffort streams are greedy Realrate streams are self controlled Realrate packets are dropped regardless of available bandwidth FCFS scheduling does not guarantee bandwidth h Reservation Mech 39sm o Informed 9 Too complex for programmers or u o Bandwidth requirements are not const 0 Inferred 9 Current schedulers use only resourcelevel information 0 Our Solution 9 Packet scheduler dynamically infers application requirements from protocol state Inferring Seminal0st I I Receiverrlost levels 0 Reoeiver s socket buffer is on a remote host 0 Data rate requirements change dynamically E Prnpnrtinn 3 122mm values D 3 Socket ampTransporl Lay rjlj rocols 1 I 0 Packet dispatcher reservationbased mechanism 0 Proportion and period controller progress driven policy RA 39 Kernel The RAMP Silwdulcr lrn kernel lmr39ll Sucker Brxchr39 Pcrr nu Queue PM TCp III Diltp1nclrer 111 C gtJJII gt Figure 3 The Packet Dispatcher in an Endhost s OS Syste Overhead Maximum Interface Th hput TCP Stream PDP CPU Utilization Maxim um Umd ec oml for full TCP Th rou g h p ut Stream MaXimum throughput Thvnllnhnllf Linux 135 741 Mbitss 941 Mbitss 25 Linux with our packet Schedule 741 Mbltss 941 Mbltss 293 21 q i l tr ts 0 Rise time tr how fast the controller response Overshoot mp how much oscillation the output has 0 Settling time ts when the result will reach stable RAM esponse Steurmvut Respnnse Eunn aumm bandwmm raumremems 75m Nears mun targethSV r 1 4 m 39n mVIHn s m V 5 E 55m 5 s 5m 4m Resvunse Me Anna 35m semmg me 05 15 1 Wm Semnd Figure 6 RAMP schedulers slepinpul response System Res1n nsiveness Results StepInput Response Buffer FillLevels Variations m a 20 SendBufF111Level mu 5 100 AdvemseW1nd0wFillLavel E J 5 I g F111LevelD1fferenue Q m a an a m E 60 g E 40 mm a 20 a 52 m BmdvndthAllocatmn a Bandw1dth Reumrement g 0 n 20 1 51 111 151 2m 251 m 1 51 101 151 201 251 Time 10ms Time 10ms IRise lime 100ms Oven hunt 25 and Settling Time 470ms Contr011er s setting PID parameters 40 04 10 and Sampling time 10ms n for Bandwidth Progressdriven Packet Scheduler P Com pe Linux Packet Scheduler V Bandwidth Allocations Bandwidth Allocations Estimated by the Receive Data Rate A 1 a n A 322 V3 in no 3 m in Q l E mquot a gt E 3 SW SW gt5 g m g 2 A A a v V39 quot39 d 3quotquot a inn 2 in a mi mu m 1 quot 1 1 1 51 1 1 151 Z 1 251 3H1 351 W1 651 5H1 1 11 21 11 61 51 E1 71 X1 91 1 1 111121111161151 Time 10ms Time 10ms quotw Reaerate Stream s Real ate Stream s Bestre 39ort Stream s Bandwidth Requirement Bandwidth Allocation Bandwidth Allocation Allocation versus Bandwidth Allocations Real Usage BeslrE m S39mm BestEff0rt Stream A 22 mmmmmkm m Am Rea1RmsueamsooKBymsSec 8 m 8 m g I am m mu E m 3 an 3 am gtgt Sun gt m Q in Q 4m V in V 3m 3 Inn 3 2m N 1m 4 on m n n 1 51 mi 151 mi 251 int 351 A01 in mi 1 51 m 151 mi 251 am 351 411 61 am Time 10ms Time 10ms m g 5 RAM location Dynamwca namwmm aHucnuun mun 6mm 4mm 2mm 39aHucamn usmg v39w Dandwwdm veqmremems usmg M Human new bulfev Hevs usmg Y2 i Lime bu ev mHeve usmg Y2 39 7 mum u ni I an 15 m Figum RAMP scheduler allucntionsversus the benchmark applxcmmn s reqnlrel39nems Variations muuuu sauna snuuu 4mm 2mm ve gym FCFS Sc duler TCP v1 mawmm Knsac mnnn anon snnn nun 2m mu behavmv Mn hgnuy bummed m eneckwnmm mm chedmev an guman by FCFS mm m i humeneck mum v1 TCPcun emanwmdw m v2 i g K g y m an mm 1 mm mum minus 2n auawmmm mum mMm mum n st quotyam emus mum mama mayquot mums maxiwm 1mm 55saw4nmhx n susawrmm 2 zsuawmnm zu 4n m Semnd Figure 7 TCP S behm im with 3 1139 F mm am pm
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'