Today we continue reading the paper on DBPowder. We were reviewing related technologies Today we will continue some more discussion. Hibernate is mentioned as an ORM that handles complex correspondence. Here developers describe mappings between the persistent classes and the relational schema in hbm files. This file is used to generate code and table. However, each time the hbm needs to be updwted, it is pretty disruptive. Even with annotations the expressibility of the mapping isn't improved. While we talk about ORM framework, we don't talk about the mark and sweep required for Graph API. Those we read in distributed computing. Here we read the paper for improvements to the mapping framework. Also we were hinting at writing Graph API for Active Directory objects CRUD. That cannot work unless AD objects CRUD works via LDAP protocol. We need proper credentials and reserved OU. And even so, will most likely require a ticketing framework for changes to be captured in audit trail.
Thursday, April 30, 2015
Wednesday, April 29, 2015
Today we continue reading the paper introducing DBPowder as we did in the previous post. We said that for complex correspondences, the developer needs to specify the complete correspondence among persistent classes and tables. which is not always possible because they are subject to change. With DBPowder, simple and complex correspondences are supported with a collaboration of a conceptual model and a navigational data usage description. During the initial rapid development, developers describe an Extended Entity Relationship model and DBPowder generates schema and classes for this model. During the latter spiral development, DBPowder introduces ObjectView, a graph based object description form over the EER model. The developers can refine their EER models and add ObjectView. and then DBPowder refines the existing relational schema and persistent classes and adds persistent classes for ObjectView.
In the discussion on related works, the authors mention ActiveRecord which is a one to one mapping between table and attributes - attributes of ActiveRecord are defined with those of the table. The advantage of this approach is that its simple but doesn;t work for complex correspondences.
Another example is the conceptual model eg. ER model as the basis such as WebML and Enterprise Objects Framework. Here schema and classes are generated from the conceptual model.
A third approach was introduced by Thiran et al which uses wrapper based ORM and applies the eight transformation operators one after the other to a target relational schema. The descriptive power is limited within these operators.
#codingexercise
GetOddNumberRangePowerSeventhRootPowerTwenty (Double [] A)
{
if (A == null) return 0;
Return A.OddNumberPowerSeventhRootPowerTwenty();
}
In the discussion on related works, the authors mention ActiveRecord which is a one to one mapping between table and attributes - attributes of ActiveRecord are defined with those of the table. The advantage of this approach is that its simple but doesn;t work for complex correspondences.
Another example is the conceptual model eg. ER model as the basis such as WebML and Enterprise Objects Framework. Here schema and classes are generated from the conceptual model.
A third approach was introduced by Thiran et al which uses wrapper based ORM and applies the eight transformation operators one after the other to a target relational schema. The descriptive power is limited within these operators.
#codingexercise
GetOddNumberRangePowerSeventhRootPowerTwenty (Double [] A)
{
if (A == null) return 0;
Return A.OddNumberPowerSeventhRootPowerTwenty();
}
Tuesday, April 28, 2015
Today we will start reading another research paper. This one is titled : DBPowder : A flexible object relational mapping framework based on a conceptual model. written by Murakami, Amagasa, Kitagawa et al. Object Relational mapping framework are well known to web application developers for the convenience they provide in programming data objects and persisting to a database. The relational schema is abstracted by an object graph that enables seamless data persistence. The authors begin by recognizing that there are many such ORM frameworks and most of them have to compromise two contradictory requirements, 1) that is the support of persistence classes that are directly mapped to relational table. and 2) the support of complicated compositions of base classes which are required by the application. These are two strong requirements and they become clearer as the application evolves. Initially a one to one mapping between each persistent class and their respective table is required and as the development proceeds, more complicated correspondences between persistent classes and relational tables are needed as the development proceeds. Foytr this reason, it is desirable for an ORM framework to be flexible enough between these two ends of the spectrum at different development stages.
In this paper, the authors do that by proposing a framework called DBPowder that addresses the difficulty in handling simple and complex correspondences. DBPowder supports direct mapping to tables with Extended Entity Relationship Model and it supports complicated compositions with ObjectView, a graph based object description form over the EER model. The EER model and the ObjctView together provide the flexibility that is required in different development stages.
Through out this paper the authors use the term simple correspondence and complex correspondence for 1) and 2) mentioned earlier. They refer to the classes in ORM as a) persistence classes that deal with persistent data in an object oriented language. b) relational schema to manage the persistent data in the RDB. and c) data conversion between object states and RDB queries and responses.
If we take the example of users and hosts, that have a many to many relationship as captured in a third join table, then we can have a simple correspondence with more complicated mappings possible by defining the mappings by hand.
In this paper, the authors do that by proposing a framework called DBPowder that addresses the difficulty in handling simple and complex correspondences. DBPowder supports direct mapping to tables with Extended Entity Relationship Model and it supports complicated compositions with ObjectView, a graph based object description form over the EER model. The EER model and the ObjctView together provide the flexibility that is required in different development stages.
Through out this paper the authors use the term simple correspondence and complex correspondence for 1) and 2) mentioned earlier. They refer to the classes in ORM as a) persistence classes that deal with persistent data in an object oriented language. b) relational schema to manage the persistent data in the RDB. and c) data conversion between object states and RDB queries and responses.
If we take the example of users and hosts, that have a many to many relationship as captured in a third join table, then we can have a simple correspondence with more complicated mappings possible by defining the mappings by hand.
Monday, April 27, 2015
Today we start reading up on Azure AD Graph API. This has let different web clients, applications and services to take advantage of doing CRUD on AD Artifacts directly. We will review some of the sample code to connect with this Graph API also. Graph APIs are as relevant to a cloud API provider as a portal to the user. In this section, we cover the usability aspect of the Graph APIs.
First of all the Azure AD Graph APIs lists entities and types and the operations that can be performed on them. These are REST based APIs so they follow the common REST standards. The entities exposed by the APIs include Application, AppRoleAssignment, Contact, Device, DirectoryLinkChange, DirectoryObject, DirectoryRole, DirectoryRoleTemplate, ExtensionProperty, Group, OAuth2PermissionGrant, ServicePrincipal, SubscribedSKU, TenantDetail, User etc.
The complex types exposed by this API include AlternativeSecurityId, AppRole, AssignedLicense, AssignedPlan, KeyCredential, LicenseUnitsDetail, OAuth2Permission, PasswordCredential, PasswordProfile, ProvisionedPlan, Provisioning Error, RequiredResourceAccess, ResourceAccess, ServicePlanInfo, ServicePrincipalAuthenticationPolicy, VerifiedDomain etc.
In addition, the API is popular for the operations on the AD artifacts such as Users, Groups, Roles and Contacts.
The Operations on Users include CreateUser, GetUser(s), UpdateUser, DeleteUser, GetUserDirectReports, Get Users GroupMemberships, Get Users manager, Update Users manager, Reset User's Password.
The Operations on Group include CreateGroup, GetGroup(s), UpdateGroup, DeleteGroup, GetGroupMembers, AddaMemberToAGroup, RemoveaMemberFromAGroup, CheckGroupMembership, CheckGroupMembershipInList, GetAllGroupMemberships (transitive).
Roles and Contacts can only be listed with this Graph APIs.
DirectoryExtensions can also be created, updated and deleted with these APIs. Directory extensions enables application developers to extend the directory and develop richer applications without worrying about the limitations exposed by an external store. For example, user, Group, TenantDetail, Device, Application, and ServicePrincipal can be extended with String Type or BinaryType Single Valued Attributes. A single string attribute can take say 256 characters and 100 such extension values are permitted on a single object. A SkypeID for a user can be taken as an extension.
#codingexercise
GetOddNumberRangeSumSeventhRootPowerTwenty (Double [] A)
{
if (A == null) return 0;
Return A.OddNumberSumSeventhRootPowerTwenty();
}
First of all the Azure AD Graph APIs lists entities and types and the operations that can be performed on them. These are REST based APIs so they follow the common REST standards. The entities exposed by the APIs include Application, AppRoleAssignment, Contact, Device, DirectoryLinkChange, DirectoryObject, DirectoryRole, DirectoryRoleTemplate, ExtensionProperty, Group, OAuth2PermissionGrant, ServicePrincipal, SubscribedSKU, TenantDetail, User etc.
The complex types exposed by this API include AlternativeSecurityId, AppRole, AssignedLicense, AssignedPlan, KeyCredential, LicenseUnitsDetail, OAuth2Permission, PasswordCredential, PasswordProfile, ProvisionedPlan, Provisioning Error, RequiredResourceAccess, ResourceAccess, ServicePlanInfo, ServicePrincipalAuthenticationPolicy, VerifiedDomain etc.
In addition, the API is popular for the operations on the AD artifacts such as Users, Groups, Roles and Contacts.
The Operations on Users include CreateUser, GetUser(s), UpdateUser, DeleteUser, GetUserDirectReports, Get Users GroupMemberships, Get Users manager, Update Users manager, Reset User's Password.
The Operations on Group include CreateGroup, GetGroup(s), UpdateGroup, DeleteGroup, GetGroupMembers, AddaMemberToAGroup, RemoveaMemberFromAGroup, CheckGroupMembership, CheckGroupMembershipInList, GetAllGroupMemberships (transitive).
Roles and Contacts can only be listed with this Graph APIs.
DirectoryExtensions can also be created, updated and deleted with these APIs. Directory extensions enables application developers to extend the directory and develop richer applications without worrying about the limitations exposed by an external store. For example, user, Group, TenantDetail, Device, Application, and ServicePrincipal can be extended with String Type or BinaryType Single Valued Attributes. A single string attribute can take say 256 characters and 100 such extension values are permitted on a single object. A SkypeID for a user can be taken as an extension.
#codingexercise
GetOddNumberRangeSumSeventhRootPowerTwenty (Double [] A)
{
if (A == null) return 0;
Return A.OddNumberSumSeventhRootPowerTwenty();
}
Sunday, April 26, 2015
Today we take a break to cover go language. This is an opensource programming language and works on Linux, Mac, Windows and more. Code is brief and explains itself succinctly. Code is organized into packages. Functions, types, constants and variables have to be exported from a package before being used with their package qualifiers.
In Go code, errors are values, checked with if err != nil syntax.
As an example, token, err := scanner.Scan()
if (err != nil) {
return err;
}
Multivalue return from functions are common. Most library code have one or two checks only per file. Types keep the data, operation and error together. So there is no need for callers to check after each call to a type. They can multiple calls and assume that an error would have triggered subsequent calls to fail.
Code is automatically organized into bin, pkg, src and referenced via paths.
Testing is available via lightweight test framework that exposes syntax such as a func ( t *testing.T). The tests call a failure function such as t.Error or t.Fail and the test functions themselves are named TestFooBar etc.
Formatting follows simple C like syntax. with fmt.Printf statements or log.Println
Interfaces are named with a convention where they end with an -er after their primary behaviour.
Allocation primitives are new and make. new does not initialize memory it only returns a zero valued address A zero value for a mutex is an unlocked mutex. A zero value of the Buffer means its empty and ready to use. Consequently those types with buffers and mutexes are initialized by the same new.
make creates slices, maps and channels only and it returns an initialized not zeroed value of type and so references to data structures must be initialized separately.
Data is represented as Arrays, slices and maps. Arrays and slices are one dimensional. Slices can be of variable lengths. Maps associate values of one type with that of another type.
Methods can be defined for any named types except pointers or interfaces and the receiver doesn't have to be a struct
In Go code, errors are values, checked with if err != nil syntax.
As an example, token, err := scanner.Scan()
if (err != nil) {
return err;
}
Multivalue return from functions are common. Most library code have one or two checks only per file. Types keep the data, operation and error together. So there is no need for callers to check after each call to a type. They can multiple calls and assume that an error would have triggered subsequent calls to fail.
Code is automatically organized into bin, pkg, src and referenced via paths.
Testing is available via lightweight test framework that exposes syntax such as a func ( t *testing.T). The tests call a failure function such as t.Error or t.Fail and the test functions themselves are named TestFooBar etc.
Formatting follows simple C like syntax. with fmt.Printf statements or log.Println
Interfaces are named with a convention where they end with an -er after their primary behaviour.
Allocation primitives are new and make. new does not initialize memory it only returns a zero valued address A zero value for a mutex is an unlocked mutex. A zero value of the Buffer means its empty and ready to use. Consequently those types with buffers and mutexes are initialized by the same new.
make creates slices, maps and channels only and it returns an initialized not zeroed value of type and so references to data structures must be initialized separately.
Data is represented as Arrays, slices and maps. Arrays and slices are one dimensional. Slices can be of variable lengths. Maps associate values of one type with that of another type.
Methods can be defined for any named types except pointers or interfaces and the receiver doesn't have to be a struct
Saturday, April 25, 2015
We continue the review of the performance results from the study of a hyper proxy streaming proxy design. We saw that with the workload we labeled 'web', the hyper proxy provides the best continuous streaming service to the client as compared to the proxy hit and the proxy startup hit schemes. Hyper proxy can reduce jitter by nearly 50% when the cache size is nearly 20 %.
Similar results are observed for the PART workload as shown in Figure 3. When cache size is nearly 20% of the the object size, hyper proxy reduces proxy jitter by 50% by giving up less than 5% in the byte hit ratio. To reduce the delayed startup ratio, the proxy startup hit achieves the best performance. The result is somewhat expected because the scheme targets the reduction in delayed startup ratio. Contrasting this with hyper proxy which aggressively reduces proxy jitter by keeping more segments, the cache space may be used by media objects for which the demand may be terminated early. This lowers the effectiveness of hyper proxy with delayed startup ratio. Lastly with the real workload, hyper proxy works best individually for each metric and overall. It performs better in reducing proxy jitter and delayed startup as well as keeping the degradation in byte hit ratio within tolerable limits.
In conclusion, we see that the proxy designs that were targeting byte hit ratio can be improved by targeting proxy jitter instead because byte hit ratio does not target continuous media delivery which is more important for streaming purposes. The authors for this paper are credited with an optimization model that improves performance against proxy jitter with a small tradeoff increase in byte hit ratio. This tradeoff has been elaborated in the previous discussions. Using this model, the authors have proposed an active prefetching method that determines which segment to bring in to the cache when. Lastly by combining prefetching with proxy caching schemes, the authors have proposed a hyper proxy system that performs well against all the performance studies mentioned.
Similar results are observed for the PART workload as shown in Figure 3. When cache size is nearly 20% of the the object size, hyper proxy reduces proxy jitter by 50% by giving up less than 5% in the byte hit ratio. To reduce the delayed startup ratio, the proxy startup hit achieves the best performance. The result is somewhat expected because the scheme targets the reduction in delayed startup ratio. Contrasting this with hyper proxy which aggressively reduces proxy jitter by keeping more segments, the cache space may be used by media objects for which the demand may be terminated early. This lowers the effectiveness of hyper proxy with delayed startup ratio. Lastly with the real workload, hyper proxy works best individually for each metric and overall. It performs better in reducing proxy jitter and delayed startup as well as keeping the degradation in byte hit ratio within tolerable limits.
In conclusion, we see that the proxy designs that were targeting byte hit ratio can be improved by targeting proxy jitter instead because byte hit ratio does not target continuous media delivery which is more important for streaming purposes. The authors for this paper are credited with an optimization model that improves performance against proxy jitter with a small tradeoff increase in byte hit ratio. This tradeoff has been elaborated in the previous discussions. Using this model, the authors have proposed an active prefetching method that determines which segment to bring in to the cache when. Lastly by combining prefetching with proxy caching schemes, the authors have proposed a hyper proxy system that performs well against all the performance studies mentioned.
Friday, April 24, 2015
Today we continue discussing the remaining modules of the Hyper proxy system and the results. There were two kinds of workloads used. The first kind of workload varied the lengths I found the media objects and the second kind of workload varied the access times of media objects such that the session would close before the full object us downloaded. In addition a third workload involving a capture from real traffic on a server was also used. These three showed different characteristics we use the two metrics to evaluate the workloads one is the delayed startup ratio and the other is a byte hit ratio. The first is the total number of startup delayed requests normalized by the total number of requests . The second is the total amount of data transferred divided by that demanded by all the clients. And we also want to reduce jitter byte ratio.
We now evaluate the performance of the workloads which we label Web for first, Part for second and Real for third. The proxy cache system was also varied to involve three different schemes. The proxy hit represents the adaptive lazy segmentation with active prefetching. The proxy startup hit represents the improved lazy segmentation scheme and active prefetching. And lastly the proxy jitter scheme which represe the hyper proxy system.
For the web workload, the Hyper Proxy provides the best continuous streaming service to the clients while the Proxy Hit ratio performs worst since it increases byte hit ratio. This is more notably so when the cache size is 20% of the total object size in which case the reduction in proxy jitter is nearly 50 % with the hyper proxy.
Hyper proxy achieves the lowest delayed startup ratio followed closely by the proxy startup hit scheme.
The hyper proxy achieves a relatively low byte hit ratio because there is a smaller reduction of network traffic.
We now evaluate the performance of the workloads which we label Web for first, Part for second and Real for third. The proxy cache system was also varied to involve three different schemes. The proxy hit represents the adaptive lazy segmentation with active prefetching. The proxy startup hit represents the improved lazy segmentation scheme and active prefetching. And lastly the proxy jitter scheme which represe the hyper proxy system.
For the web workload, the Hyper Proxy provides the best continuous streaming service to the clients while the Proxy Hit ratio performs worst since it increases byte hit ratio. This is more notably so when the cache size is 20% of the total object size in which case the reduction in proxy jitter is nearly 50 % with the hyper proxy.
Hyper proxy achieves the lowest delayed startup ratio followed closely by the proxy startup hit scheme.
The hyper proxy achieves a relatively low byte hit ratio because there is a smaller reduction of network traffic.
Thursday, April 23, 2015
We discussed the hyper proxy modules for Active prefetching and lazy segmentation strategy. We continue discussing the remaining two modules. We briefly looked at the replacement policy and the maintainance of two lists - basic and premium lists. The utility value of each object is updated after each replacement. Even after an object is fully evicted, the system will keep its access log. If this is not the case, when the object is accessed again, it will be fully cached.One characteristic of media objects is that they have diminishing popularity as the time goes by. Hence this recaching the full length of the object is wasteful. Consequently keeping the access log is relevant and recommended.
To not let access logs proliferate, a large enough timeout threshold is set so that the proxy deletes the access logs eventually.
We now look at performance evaluation. To evaluate the performance of the proxy, it was tested on several workloads - both real and synthetic. All the workloads assumed a Zipf like distribution with a skew factor of theta. All the media objects and the request interval follow the Poisson distribution with a mean interval lambda.
The first synthetic workload simulates accesses to the media object in the web environment in which the media varies from short one to long one. All there parameters are considered same.
The second workload simulates the web access where the clients abort the access where a started session terminates before the full media object is delivered.Nearly 80%of the sessions terminated before 20% of the object is delivered.
The third workload is a real capture of a workload covering a period of 10 days from an actual server.
There are a total of 403 objects and the unique object size accounts to 20GB. A total of 9000 requests were made during the period mentioned for the real workload.
To not let access logs proliferate, a large enough timeout threshold is set so that the proxy deletes the access logs eventually.
We now look at performance evaluation. To evaluate the performance of the proxy, it was tested on several workloads - both real and synthetic. All the workloads assumed a Zipf like distribution with a skew factor of theta. All the media objects and the request interval follow the Poisson distribution with a mean interval lambda.
The first synthetic workload simulates accesses to the media object in the web environment in which the media varies from short one to long one. All there parameters are considered same.
The second workload simulates the web access where the clients abort the access where a started session terminates before the full media object is delivered.Nearly 80%of the sessions terminated before 20% of the object is delivered.
The third workload is a real capture of a workload covering a period of 10 days from an actual server.
There are a total of 403 objects and the unique object size accounts to 20GB. A total of 9000 requests were made during the period mentioned for the real workload.
Wednesday, April 22, 2015
We discuss the remaining three major modules in the HyperProxy design. Active prefetching helps with every subsequent access to a media object. It helps determine when to prefetch which segment.
In the case when no segment is cached, the prefetching of the Bs/Bt segment is considered.The new segment admission is marked with priority
If there are a few segments cached that number less than the Bs/Bt threshold, then the proxy jitter is unavoidable. The new segment admission is marked with priority.
IF there are more segments cached than the said threshold, the prefetching of the next segment starts at an offset Bs/Bt number of segments from this candidate. The new segment admission is marked with non-priority.
Bs is the encoding rate of the segment and Bt is the network bandwidth of the proxy server link.
Active prefetching of exponentially segmented object.
Next we consider the lazy segmentation strategy. When there is no cache space available and replacement is needed, the replacement policy kicks in and calculates the caching utility of each cached object. The smallest utility value items are evicted first. If the object is fully cached, the object is segmented uniformly based on the average access duration at the time. Then a certain number of segments are retained and the rest are evicted.
The replacement policy uses a formula to determine the utility value and the eviction is based on the maintenance of two lists - the basic list and the priority list
In the case when no segment is cached, the prefetching of the Bs/Bt segment is considered.The new segment admission is marked with priority
If there are a few segments cached that number less than the Bs/Bt threshold, then the proxy jitter is unavoidable. The new segment admission is marked with priority.
IF there are more segments cached than the said threshold, the prefetching of the next segment starts at an offset Bs/Bt number of segments from this candidate. The new segment admission is marked with non-priority.
Bs is the encoding rate of the segment and Bt is the network bandwidth of the proxy server link.
Active prefetching of exponentially segmented object.
Next we consider the lazy segmentation strategy. When there is no cache space available and replacement is needed, the replacement policy kicks in and calculates the caching utility of each cached object. The smallest utility value items are evicted first. If the object is fully cached, the object is segmented uniformly based on the average access duration at the time. Then a certain number of segments are retained and the rest are evicted.
The replacement policy uses a formula to determine the utility value and the eviction is based on the maintenance of two lists - the basic list and the priority list
Tuesday, April 21, 2015
Today we continue discussing the hyper proxy from the paper on streaming proxy design. We saw that it maintains a data structure that keeps the threshold length, the average access duration, the access frequency F etc. The system maintains two media object lists - one premium list and one basic list. These lists help to find a victim and evict some of its segments. Then the segments of new objects are adaptively admitted by the admission policy.
There are four major modules in the Hyper Proxy caching system. These are:
1) a priority based admission policy
2) Active prefetching
3) Lazy segmentation policy
4) Differentiated replacement policy
We discuss these in detail in the next few posts.
#codingexercise
GetOddNumberRangeProductFifthRootSumEighteen (Double [] A)
{
if (A == null) return 0;
Return A.OddNumberProductFifthRootSumEighteen();
}
We will continue our discussion about the major modules in the Hyper Proxy system.
Let's begin with the cache admission system. As we mentioned before, if the media object is requested the first time, the object is then cached in full. The replacement policy is activated if there is not sufficient space. From the two lists, we look at the premium list first, we pick out an object for which there is no priority and if one such is not located, we look at one with a priority. The fully cached object is linked to the basic list and an access log is created. If the access log indicated that the object is fully cached, the access log is merely updated to handle this robustness case.
The other three major modules are Active Prefetching, Lazy segmentation policy, differentiated replacement policy.
In the active prefetching module, partially cached objects so called because they don't have all the segments in the cache are then determined to see which segments should be prefetched.
In the lazy segmentation module, the average access duration at current time instance is calculated. It is used as the length of the base segment. and then the object is segmented uniformly Then a number of segments determined by the ration threshold length over base length is retained while the rest evicted.
In the differentiated replacement policy, we give a higher priority to reduce proxy jitter, reduces the erroneous decision of the replacement and gives fair chance to the replacement segment so that they can be cached back into the proxy again based on admittance policy should media objects be accessed again.
There are four major modules in the Hyper Proxy caching system. These are:
1) a priority based admission policy
2) Active prefetching
3) Lazy segmentation policy
4) Differentiated replacement policy
We discuss these in detail in the next few posts.
#codingexercise
GetOddNumberRangeProductFifthRootSumEighteen (Double [] A)
{
if (A == null) return 0;
Return A.OddNumberProductFifthRootSumEighteen();
}
We will continue our discussion about the major modules in the Hyper Proxy system.
Let's begin with the cache admission system. As we mentioned before, if the media object is requested the first time, the object is then cached in full. The replacement policy is activated if there is not sufficient space. From the two lists, we look at the premium list first, we pick out an object for which there is no priority and if one such is not located, we look at one with a priority. The fully cached object is linked to the basic list and an access log is created. If the access log indicated that the object is fully cached, the access log is merely updated to handle this robustness case.
The other three major modules are Active Prefetching, Lazy segmentation policy, differentiated replacement policy.
In the active prefetching module, partially cached objects so called because they don't have all the segments in the cache are then determined to see which segments should be prefetched.
In the lazy segmentation module, the average access duration at current time instance is calculated. It is used as the length of the base segment. and then the object is segmented uniformly Then a number of segments determined by the ration threshold length over base length is retained while the rest evicted.
In the differentiated replacement policy, we give a higher priority to reduce proxy jitter, reduces the erroneous decision of the replacement and gives fair chance to the replacement segment so that they can be cached back into the proxy again based on admittance policy should media objects be accessed again.
Monday, April 20, 2015
Today we continue to discuss the streaming proxy design. We were discussing to improve tje lazy segmentation strategy. The replacement policy involves evicting the least useful media object segments. This can be done in one of three different phases. the first phase is when the object is fully cached. the second phase is when the object is partially cached with more than one segment. The third phase is when the object is partially cached with only one segment. The utility value of each object is updated after each replacement and this process repeats iteratively until the required space is found.
We now discuss the hyper proxy system where the authors co-ordinate the two schemes discussed earlier.
For every media object accessed through the proxy, a data structure is maintained which is called the access log of the object. This data structure has fields for such things as the length of the base segment, the number of cached segments of the object, the threshold length used in the replacement policy and the average access duration of an object. The threshold length is calculated for each object as per the three phase technique above. In this system, there are two lists maintained, the basic list and the premium list. The basic list contains all objects whose length of cached segment is larger than the length of all its threshold length while the premium list contains those objects whose cached data length is equal to or less than the threshold length. A flag is used to determine the priority at admission. The admission policy dictates that the object is fully cached until it is chosen as an eviction item. At that time, some of the segments are evicted, the object is also transferred to the premium list. When the object is accessed again, the segments of the object are adaptively admitted by the admission policy or adaptively replaced by the replacement policy
We now discuss the hyper proxy system where the authors co-ordinate the two schemes discussed earlier.
For every media object accessed through the proxy, a data structure is maintained which is called the access log of the object. This data structure has fields for such things as the length of the base segment, the number of cached segments of the object, the threshold length used in the replacement policy and the average access duration of an object. The threshold length is calculated for each object as per the three phase technique above. In this system, there are two lists maintained, the basic list and the premium list. The basic list contains all objects whose length of cached segment is larger than the length of all its threshold length while the premium list contains those objects whose cached data length is equal to or less than the threshold length. A flag is used to determine the priority at admission. The admission policy dictates that the object is fully cached until it is chosen as an eviction item. At that time, some of the segments are evicted, the object is also transferred to the premium list. When the object is accessed again, the segments of the object are adaptively admitted by the admission policy or adaptively replaced by the replacement policy
Sunday, April 19, 2015
As we read up on this streaming proxy design, we will continue to review the analytical results from the tradeoff between delay startup ratio and the byte hit ratio. What we had said so far was that the change in the delay with respect to the change in the byte hit is always greater than 1 when the percentage of the startup length and the percentage of the reserved cache space is less than 50%. This gives a solid basis to giving a higher priority to the caching of the startup length of objects in the replacement policy. We now study the proposed replacement policy design.
This technique is called the improved adaptive lazy segmentation strategy. In order to significantly reduce the startup latency with a small decrease of byte hit ratio, a three phase iterative replacement policy is considered. The least utility value media object is chosen as the victim for eviction from the cache.And the segment of this object is evicted in one of two phases as follows:
In the first phase, if the object is fully cached, the object is segmented by the lazy segmentation method The first two segments are kept and the remaining segments are evicted right after the segmentation is completed.
In the second phase, if the object is partially cached with more than one segment, the last cached segment of this object is evicted.
In the third phase, if the victim has only the first segment and is to be replaced, then its startup length and base segment length is compared. If the startup length is less than the base segment length, the base segment length is kept and the rest is replaced. Otherwise it is totally replaced. The utility value of the media object is updated after each replacement and this process repeats iteratively until the required space is found.
#codingexercise
GetOddNumberRangeSumFifthRootSumEighteen (Double [] A)
{
if (A == null) return 0;
Return A.OddNumberSumFifthRootSumEighteen();
}
This technique is called the improved adaptive lazy segmentation strategy. In order to significantly reduce the startup latency with a small decrease of byte hit ratio, a three phase iterative replacement policy is considered. The least utility value media object is chosen as the victim for eviction from the cache.And the segment of this object is evicted in one of two phases as follows:
In the first phase, if the object is fully cached, the object is segmented by the lazy segmentation method The first two segments are kept and the remaining segments are evicted right after the segmentation is completed.
In the second phase, if the object is partially cached with more than one segment, the last cached segment of this object is evicted.
In the third phase, if the victim has only the first segment and is to be replaced, then its startup length and base segment length is compared. If the startup length is less than the base segment length, the base segment length is kept and the rest is replaced. Otherwise it is totally replaced. The utility value of the media object is updated after each replacement and this process repeats iteratively until the required space is found.
#codingexercise
GetOddNumberRangeSumFifthRootSumEighteen (Double [] A)
{
if (A == null) return 0;
Return A.OddNumberSumFifthRootSumEighteen();
}
Saturday, April 18, 2015
Today we continue on our discussion of the streaming proxy design. We were finding the upper bound on the byte hit ratio and the startup ratio in the ideal case. Let us look into some analytical results to give us an understanding of these ratios in the ideal case. Given a total of 10000 original media objects where we use a cache with a size of 20% of the total object size, we initialize the number of objects possible with the average length of objects to be 2000. Skew ratio is set at 0.47 and the startup length percentage is set at 5%. It is observed that the decrease in the byte hit ratio is much slower than the decrease of the delayed startup ratio when B increases. This implies that if we reduce the byte hit ratio by a small measure, we can trade for a significant large reduction in the delayed startup ratio. This has been an objective of the proxy design principles. To find this tradeoff, the partial derivative of the upper bound on the delay startup ratio with respect to the reserved cache space percentage is calculated. This yields the change in the delayed startup ratio. Similarly the partial derivative of the upper bound on the byte hit ratio with respect to the reserved cache space percentage yields the change in the byte hit ratio. From a relation with the change in delayed startup ratio over the change in byte hit ratio, it can be shown that the delta delay over the delta hit is always greater than 1 when alpha and Beta are less than 50%.
#codingexercise
GetOddNumberRangeSumCubeRootSumEighteen (Double [] A)
{
if (A == null) return 0;
Return A.OddNumberSumCubeRootSumEighteen();
}
#codingexercise
GetOddNumberRangeSumCubeRootSumEighteen (Double [] A)
{
if (A == null) return 0;
Return A.OddNumberSumCubeRootSumEighteen();
}
Friday, April 17, 2015
Today we continue our discussion on streaming proxy design. We were discussing the ideal case for the analytical model. We said that it corresponds to when the cache is always used to populate the most popular media objects. In this case, the delayed startup ratio was the ratio of the mean arrival rate of the t+1th to Nth media object over that of all of the media objects. Representing this in terms of the skew ratio,we notice that the upper bound is when skew factor is not equal to 1. We can now find the byte hit ratio in this case. Again, we find the upper bound by using t = Beta .U / Alpha where U is the the total cache size divided by the average length of objects. t was the number of most popular objects sorted by popularity whose segments within the startup length would fill the reserved portion of the cache size. The max delay startup ratio occurs when skew factor is not equal to 1. We can express this in the same ratio of arrival rates as the definition of the delay startup ratio.
Next to derive an upper bound on the byte hit ratio in the ideal case, let us consider the misses when the object is accessed for the first time. The byte hit ratio in this case is expressed as 1 minus a ratio where the numerator is the startup length of the t+1th to the Nth objects times the average arrival rate and that of the beyond-startup-length of the q+1 th to the Nth media objects times the average arrival rate and the denominator is the full length of all the N media objects times the average arrival rate.
The reason we subtract it from one is because we want the remaining that corresponds to the non-reserved cache space.
#codingexercise
GetOddNumberRangeSumCubeRootPowerEighteen) (Double [] A)
{
if (A == null) return 0;
Return A.OddNumberSumCubeRootPowerEighteen();
}
Next to derive an upper bound on the byte hit ratio in the ideal case, let us consider the misses when the object is accessed for the first time. The byte hit ratio in this case is expressed as 1 minus a ratio where the numerator is the startup length of the t+1th to the Nth objects times the average arrival rate and that of the beyond-startup-length of the q+1 th to the Nth media objects times the average arrival rate and the denominator is the full length of all the N media objects times the average arrival rate.
The reason we subtract it from one is because we want the remaining that corresponds to the non-reserved cache space.
#codingexercise
GetOddNumberRangeSumCubeRootPowerEighteen) (Double [] A)
{
if (A == null) return 0;
Return A.OddNumberSumCubeRootPowerEighteen();
}
Thursday, April 16, 2015
Today we continue our discussion on streaming proxy design. We were reviewing the assumptions for building an analytical model. The first assumption is that the popularity of media objects follows a zipf distribution. The second assumption was that the request arrival interval process occurs at a known average rate and independent of time. The third assumption was that the clients view the media objects completely. The first assumption gives us a probability set pi. The second assumption gives us a sampling process where the sum of pi equals 1. The third assumption gives us a mean arrival rate as lambda times pi. We also reviewed the added definition of startup length. This is the percentage alpha of the full length of the media object. And Beta is the percentage of the total cache space reserved for all the startup lengths.
This help us determine the startup ratio. To build the model, we consider the ideal case that the cache space is allocated to cache the most popular objects, then the startup lengths of the first t most popular objects can remain in the reserved portion of the cache. This can be extended to imply that the rest of the cache is used for the q most popular objects beyond their startup length. Therefore the delayed startup ratio can be expressed as the sum of the mean arrival rate of the t+1th to the Nth media object over that of all the N media objects.
#codingexercise
GetOddNumberRangeSumCubeRootPowerSixteen) (Double [] A)
{
if (A == null) return 0;
Return A.OddNumberSumCubeRootPowerSixteen();
}
This help us determine the startup ratio. To build the model, we consider the ideal case that the cache space is allocated to cache the most popular objects, then the startup lengths of the first t most popular objects can remain in the reserved portion of the cache. This can be extended to imply that the rest of the cache is used for the q most popular objects beyond their startup length. Therefore the delayed startup ratio can be expressed as the sum of the mean arrival rate of the t+1th to the Nth media object over that of all the N media objects.
#codingexercise
GetOddNumberRangeSumCubeRootPowerSixteen) (Double [] A)
{
if (A == null) return 0;
Return A.OddNumberSumCubeRootPowerSixteen();
}
Tuesday, April 14, 2015
Today we continue our discussion on streaming proxy design. We were saying that the reality is that cache size may be bounded. We may not be able to cache the number of segments required for continuous delivery of a media object if there are lots of media objects. One way to overcome this was to determine the priority of media objects. Given a higher priority in reducing proxy jitter, the proxy can choose to evict segments of the object whose cached data length is less than its prefetching length. This will allow the prefetching of the cached segment to be always in time. Even if the segments of popular objects are evicted, the overall proxy jitter reduces at the cost of a little byte hit ratio. Thus we have seen that the byte hit ratio can be traded for less proxy jitter.
This conflict between improving the byte hit ratio and reducing the proxy jitter helped the authors to revise the principle of designing a better proxy based on proxy jitter. They noted that segment based proxy caching strategies always perform well in the byte hit ratio but not so well in the delayed startup ratio. This is further explained when evaluating the adaptive lazy segmentation based scheme.
We also look at the tradeoff between Byte hit ratio and delayed startup ratio. We could see some conflicting interests in this tradeoff from the previous discussion but we build an analytical model now. This analytical model is based on the following assumptions:
1) The popularity of the objects follow a Zipf like distribution
2) The request arrival interval process follows a Poisson distribution with a mean arrival rate lambda.
3) The clients view the requested objects completely. This is to simplify the analysis and does not affect the conclusion.
After we build the model, we will evaluate it with analytical results.
Then we review the author's improved Adaptive-Lazy Segmentation Strategy.
The assumption 1) describes the probability set pi in terms of the fraction of fi to the total fi. fi is the inverse of i raised to the power theta and i can vary from 1 to N the total number of objects. Theta is the skew factor and is positive.
The assumption 2) describes the sampling process as independent and sampled from the aggregate arrival interval process based on probability set pi where the sum of pi equals 1.
The assumption 3) lets us calculate the mean arrival rate as lambda times pi.
In addition to these assumptions, the following definitions make it easier to calculate the delayed startup ratio.
The startup length is the length of the beginning part of an object. If this part is cached, then there is no startup delay. Let alpha be this percentage of the full object length. Let Beta be the percentage of the total cache space reserved for caching the startup lengths of objects.
This conflict between improving the byte hit ratio and reducing the proxy jitter helped the authors to revise the principle of designing a better proxy based on proxy jitter. They noted that segment based proxy caching strategies always perform well in the byte hit ratio but not so well in the delayed startup ratio. This is further explained when evaluating the adaptive lazy segmentation based scheme.
We also look at the tradeoff between Byte hit ratio and delayed startup ratio. We could see some conflicting interests in this tradeoff from the previous discussion but we build an analytical model now. This analytical model is based on the following assumptions:
1) The popularity of the objects follow a Zipf like distribution
2) The request arrival interval process follows a Poisson distribution with a mean arrival rate lambda.
3) The clients view the requested objects completely. This is to simplify the analysis and does not affect the conclusion.
After we build the model, we will evaluate it with analytical results.
Then we review the author's improved Adaptive-Lazy Segmentation Strategy.
The assumption 1) describes the probability set pi in terms of the fraction of fi to the total fi. fi is the inverse of i raised to the power theta and i can vary from 1 to N the total number of objects. Theta is the skew factor and is positive.
The assumption 2) describes the sampling process as independent and sampled from the aggregate arrival interval process based on probability set pi where the sum of pi equals 1.
The assumption 3) lets us calculate the mean arrival rate as lambda times pi.
In addition to these assumptions, the following definitions make it easier to calculate the delayed startup ratio.
The startup length is the length of the beginning part of an object. If this part is cached, then there is no startup delay. Let alpha be this percentage of the full object length. Let Beta be the percentage of the total cache space reserved for caching the startup lengths of objects.
Monday, April 13, 2015
today we continue our discussion on the design of streaming proxy. we were calculating the number of segments for continuous delivery. We were considering both th uniformly segmented media and the exponentially segmented media. We now review the tradeoff between the low proxy jitter and the high byte ratio and then the byte hit ratio versus the delayed startup ratio.In theory, we know the minimum number of segments that must always be cached in the proxy to guarantee a proxy jitter free delivery. In practice, this is difficult for each and every media object because cache size is limited. One way to overcome this is to determine if a media object is popular. Popular objects are always cached to reduce network traffic and server load. If an object is popular enough all its segments can be cached in the proxy even larger than the prefetching length. On the other hand, if the objects are not popular enough, some segments may get evicted and only a few of it's segments cached. This can contribute to proxy jitter. Given a higher priority in reducing the proxy jitter, the proxy can choose to evict segments of the object whose cached data length is larger than its prefetching length so that the prefetching of its uncached segments can always be in time. If the popular objects get evicted by any chance, this would contribute to the byte hit ratio. Thus we can simulate the availability of all segments for media objects that are popular.
Sunday, April 12, 2015
We continue the coverage of some JavaScript libraries. We resume with the next library in the list mentioned. This is groupie. groupie provides semantics of a group where all functions are executed at once and a chain where they are executed in the declared order. The function registrations for group or chain is similar to the previous ones we have seen from the list.
The next library in the list is continuables which exposes the semantics that a unit continuables can be fulfilled. Consequently, many of the can be grouped or chained. What sets this library apart is the ease of use for node.js developers. For example:
Var async_fn = function(Val){
Var continuable = continuables.create();
Process.nextTick(function(){
Continuable.fulfill(Val);
});
Return continuable;
}
Now the continuables can be chained . If the chain ends with error it will be thrown. To prevent the continuable must return something. Therefore error and success cases can be differentiated based on the presence of return values and separate callbacks for these two states can be invoked via continuables.either
Slide exposes semantics similar to Async library and functions registered should not be throwing an error and instead pass it to the callback. The node.js has similar constructs in its low level but this library is puportedly easier. The convention introduces two kinds of functions. actors that take action, callbacks get results.callbacks handle all errors and is therefore the first argument. Callbacks can trap/call other callbacks. Actors pass a callback as the last argument. Actors must not throw and the return value is ignored. The library has a construct called asyncMap which is similar to the group functionality mentioned earlier. Essentially it waits for all the registered actors and callback to be complete. It also has a chain construct that enables one by one continuation.
Step is another library that enable parallel execution in addition and similar error handling.
The next library in the list is continuables which exposes the semantics that a unit continuables can be fulfilled. Consequently, many of the can be grouped or chained. What sets this library apart is the ease of use for node.js developers. For example:
Var async_fn = function(Val){
Var continuable = continuables.create();
Process.nextTick(function(){
Continuable.fulfill(Val);
});
Return continuable;
}
Now the continuables can be chained . If the chain ends with error it will be thrown. To prevent the continuable must return something. Therefore error and success cases can be differentiated based on the presence of return values and separate callbacks for these two states can be invoked via continuables.either
Slide exposes semantics similar to Async library and functions registered should not be throwing an error and instead pass it to the callback. The node.js has similar constructs in its low level but this library is puportedly easier. The convention introduces two kinds of functions. actors that take action, callbacks get results.callbacks handle all errors and is therefore the first argument. Callbacks can trap/call other callbacks. Actors pass a callback as the last argument. Actors must not throw and the return value is ignored. The library has a construct called asyncMap which is similar to the group functionality mentioned earlier. Essentially it waits for all the registered actors and callback to be complete. It also has a chain construct that enables one by one continuation.
Step is another library that enable parallel execution in addition and similar error handling.
Saturday, April 11, 2015
There are quite a few patterns in the use of Javascript. Here we cover a few.
1) Async This pattern is able to flatten the nested callbacks usually seen with making one call after the other.
a. For example if we have
i. getMoney(err, success){
if (err || !success)
throw Error(‘Oops!’);
callSweetheart(err, success{
b. Then this can be serialized with
Async.chain( function getMoney(callback) {
earn();
callback(null);
},
function callSweetheart(callback) {
dial();
callback(null);
},
Function (err){ // callback
If(err){
Console.log(err);
}
});
c. Chain also does more than serialization and consolidation of callback. It passes the result of one function as a parameter into the other. The parameters are dependent entirely on the previous function except for the last one which must be a callback.
d. Async.series is also available. This takes multiple functions in series.Each task takes the callback as a parameter. When all the functions are run or if there is an error, then the function is called with the combined results of all tasks in the order they were run.
var counter = 0;
Async.series([
Function(done) {
Console.log(counter++); // == 0
Done(null, 1);
}),
Function(done){
Console.log(counter++); // == 1
Done(null, 2,3);
}],
Function (err, one, two) {
Console.log(err); // = null;
Console.log(one); // = 1
2 / 2
Console.log(two); // == [1,2]
}
);
e. Async.parallel is also available. The tasks may not run in the same order as they appear in the array.
2) Flow.js function defines capabilities very similar to the above. The flow.exec is a convenience function that defines a flow and executes it immediately, passing no arguments to the firstfunction.
a. Flow.exec(function(){
Dosomething(this);
}, function(err){
If (err) throw err;
DoSomethingElse(this);
}, function (err, result){
If(err)throw err;
Console.log(result);
}
);
b. Sometimes a step in a flow may need to initiate several asynchronous tasks and wait onall of them before proceeding to the next step. This is called multiplexing and is achieved by passing this.MULTI() instead of this as the callback parameter.
Flow.exec(function(){
doSomething(this);
},function(param){
doSomethingDifferent(param1, this.MULTI());
doSomethingDifferent(param2, this.MULTI());
}, function(){
Okwearedone();
}
});
c. There is another convenience function called serialForEach which can be used to apply an asynchronous function to each element in an array of values serially.
3) next we discuss the following libraries:
funk,
futures
groupie
node-continuables
SlideStep
node-inflow
Node-inflow
,
Funk is a software module that provides the following syntax to serialize and parallelize callbacks.
Var funk = require('funk')('serial'); // ctor
Funk.set ('foo', 'bar'); // save results to be called in run ()
//add callback to be executed either in series or parallel:
SetTimeout(funk.add (err, success){
}, 200);
SetTimeout (funk.add (err, success){
},100);
SetTimeout (funk.nothing (), 200);
SetTimeout (funk.nothing (), 100);
Funk.run (); // both timeout will be called
Future or FuturesJS is another asynchronous toolkit
It provides constructs like
Join
ForEachAsync
ArrayAsync,
- someAsync
- FilterAsync,
- everyAsync,
- mapAsync,
- reduceAsync,
Join calls any number of asynchronous calls together similar to how pthread_join works or the then() promise works.
Var join = window.create ();
SetTimeout(join.add (), 200);
SetTimeout(join.add (), 100);
Join.notify (function (index, args){
Console.log (" callback # " + index + " " + args);
});
ArrayAsync provides asynchronous counterpart for each of the Array iterate methods.
FilterAsync(['dogs', 'cats', 'octocats'], function ( next, element){
Do (element) function (likesIt){
next(likesIt);
})
}).then (function (newArr){
DisplayLikes(newArr);
})
})();
Friday, April 10, 2015
Today we continue reading the paper on the design of streaming proxy systems.
We discussed the uniform and exponentially segmented media objects.
We talked about prefetching and minimum buffer size for such media. The minimum buffer size ensures low resource usage. The pre-fetching gives the scheduling point. It doesn't mean that the jitter can be avoided in all cases. The uniformly segmented media object has an advantage over the exponentially segmented object. It enables in-time prefetching which can begin at a later stage. Even so, continuous media streaming has not been guaranteed. One suggestion might be to keep enough segments cached. this leads us to define a prefetching length as the minimum length of the data that must be cached in the proxy in order to guarantee the continuous delivery when Bs > Bt. Prefetching is not necessary when Bs < Bt. Bs is the encoding rate and Bt is the network bandwidth averages respectively. Prefetching length aggregates cached segment length without breaks. Therefore we calculate the number of segments m for continuous delivery. In the case of uniform segmented media objects each segment length is the same. In the case of the exponentially segmented media objects, each cached segment length is twice that of the previous. We review the tradeoff between low proxy jitter and high byte ration and then they byte-hit ratio versus the delayed startup ratio.
#codingexercise
GetEvenNumberRangeSumCubeRootPowerFourteen) (Double [] A)
{
if (A == null) return 0;
Return A.EvenNumberSumCubeRootPowerFourteen();
}
We will take a short break now.
We discussed the uniform and exponentially segmented media objects.
We talked about prefetching and minimum buffer size for such media. The minimum buffer size ensures low resource usage. The pre-fetching gives the scheduling point. It doesn't mean that the jitter can be avoided in all cases. The uniformly segmented media object has an advantage over the exponentially segmented object. It enables in-time prefetching which can begin at a later stage. Even so, continuous media streaming has not been guaranteed. One suggestion might be to keep enough segments cached. this leads us to define a prefetching length as the minimum length of the data that must be cached in the proxy in order to guarantee the continuous delivery when Bs > Bt. Prefetching is not necessary when Bs < Bt. Bs is the encoding rate and Bt is the network bandwidth averages respectively. Prefetching length aggregates cached segment length without breaks. Therefore we calculate the number of segments m for continuous delivery. In the case of uniform segmented media objects each segment length is the same. In the case of the exponentially segmented media objects, each cached segment length is twice that of the previous. We review the tradeoff between low proxy jitter and high byte ration and then they byte-hit ratio versus the delayed startup ratio.
#codingexercise
GetEvenNumberRangeSumCubeRootPowerFourteen) (Double [] A)
{
if (A == null) return 0;
Return A.EvenNumberSumCubeRootPowerFourteen();
}
We will take a short break now.
Thursday, April 9, 2015
Today we will continue our discussion on the design of streaming proxy systems. We were discussing active prefetching. Prefetching schemes can reduce proxy jitter by fetching uncached segments before they are accessed. We discussed the cases of both uniformly segmented as well as exponentially segmented media object For the uniformly segmented scheme, the segments take equal amount of time. Consequently, the segments upto the ratio of Bs/Bt cause proxy jitter. This threshold is determined based on the latest that a segment needs to be fetched. Recall that this position is determined such that the time it takes to prefetch this segment should not exceed the time that it takes to deliver the rest of the cached data and the fetched data. The minimum buffer size is calculated accordingly as (1- Bt/Bs) L1. This is true for all ranges namely the first cached segment, the cached segments upto the threshold and the cached segments beyond the threshold and after.
In the case of the exponentially segmented object, a similar analysis can be done. Here, we assume Bs <= 2 Bt. When it is not so, no prefetching of uncached segments can be in time for the exponentially segmented objects. If n is the number of cached segments, then for n = 0, we have to prefetch upto (1 + log-base-2(1/(2-Bs/Bt)) segment is necessary to avoid proxy jitter in the cases thereafter. The minimum buffer size is calculated by using this threshold in the same kind of calculation as above. For n > 0 and less than the threshold, the proxy starts to prefetch the threshold segment once the client starts to access this object. The jitter is unavoidable between the n+1 th segment to threshold segment and the minimum buffer size is Li times Bt/Bs where Li is that of the threshold. For segments that are larger than the threshold, the prefetching of the n+1th segment starts when the client accesses the first 1 - 2^n / (2 ^n - 1) ( Bt / Bs - 1) portion of the first n cached segment. The minimum buffer size is Ln+1 * Bt / Bs and increases exponentially for later segments.
In the case of the exponentially segmented object, a similar analysis can be done. Here, we assume Bs <= 2 Bt. When it is not so, no prefetching of uncached segments can be in time for the exponentially segmented objects. If n is the number of cached segments, then for n = 0, we have to prefetch upto (1 + log-base-2(1/(2-Bs/Bt)) segment is necessary to avoid proxy jitter in the cases thereafter. The minimum buffer size is calculated by using this threshold in the same kind of calculation as above. For n > 0 and less than the threshold, the proxy starts to prefetch the threshold segment once the client starts to access this object. The jitter is unavoidable between the n+1 th segment to threshold segment and the minimum buffer size is Li times Bt/Bs where Li is that of the threshold. For segments that are larger than the threshold, the prefetching of the n+1th segment starts when the client accesses the first 1 - 2^n / (2 ^n - 1) ( Bt / Bs - 1) portion of the first n cached segment. The minimum buffer size is Ln+1 * Bt / Bs and increases exponentially for later segments.
Wednesday, April 8, 2015
We continue reading the paper on the design of high quality streaming proxy systems. We were reviewing Active prefetching. For a media content with uniform segmentation, we calculated the minimum buffer length to be the same in all three cases - the first segment, segments upto Bt/Bs and the segments thereafter. We also found the proxy jitter is unavoidable until the threshold.
We now do active pre-fetching for exponentially segmented object. Here we assume Bs < twice Bt. the average rate of a specific segment is less than twice the average network bandwidth. When Bs >= 2 Bt, no prefetching of the uncached segments can be in time for the exponentially segmented objects.
For the case with no segment cached, Proxy jitter in this case is inevitable.
For the case with the number of cached segments n to be between 0 and 1 + log-base-2( 1 / (2 - Bs/Bt)) threshold. The proxy starts to prefetch the next segment once the client starts to access this object. When the client accesses the segments between n+1 to the threshold, the proxy jitter becomes inevitable and the number of and the minimum buffer size is the length of this segment at the threshold * Bt/Bs.
#codingexercise
We now do active pre-fetching for exponentially segmented object. Here we assume Bs < twice Bt. the average rate of a specific segment is less than twice the average network bandwidth. When Bs >= 2 Bt, no prefetching of the uncached segments can be in time for the exponentially segmented objects.
For the case with no segment cached, Proxy jitter in this case is inevitable.
For the case with the number of cached segments n to be between 0 and 1 + log-base-2( 1 / (2 - Bs/Bt)) threshold. The proxy starts to prefetch the next segment once the client starts to access this object. When the client accesses the segments between n+1 to the threshold, the proxy jitter becomes inevitable and the number of and the minimum buffer size is the length of this segment at the threshold * Bt/Bs.
#codingexercise
GetAllNumberRangeSumCubeRootPowerFourteen) (Double [] A)
{
if (A == null) return 0;
Return A.AllNumberSumCubeRootPowerFourteen();
}
#codingexercise
GetAllNumberRangeProductCubeRootPowerSixteen) (Double [] A)
{
if (A == null) return 0;
Return A.AllNumberProductCubeRootPowerSixteen();
}
Tuesday, April 7, 2015
We discuss active prefetching from the paper "designs of high quality streaming proxy systems" by Chen, Wee and Zhang. The objective of active prefetching is to determine when to fetch which uncached segment so that proxy jitter is minimized. The paper assumes the media objects are segmented, the bandwidth is sufficient to stream the object smoothly and that each segment can be fetched in a unicast channel. Each media object has its inherent encoding rate - this is the playback rate and is denoted with an average value. Prior session data transmission rates are noted.
For a requested media object, if there are n segments cached in the proxy, then the objective is to schedule the prefetching of the n+1 th segment so that proxy jitter is avoided. At position x, the length of the to be delivered data is L-x and the Assuming Bs as the average playback rate and Bt as the average data transfer rate, we avoid proxy jitter when the time to transfer sum of all such remaining lengths L-x for each of the n segments and the n+1 segment over Bs is greater than the time for the the n+1 th segment over the average data transfer rate.
This is a way of saying that the prefetch time must not exceed the delivery time. From the equation above, the position can be varied such that the latest prefetch scheduling point is one where the arrival is just sufficient to meet demand. The buffer size would then reach minimum.
Determining the prefetching scheduling point should then be followed by a prefetching scheme and resource requirements.
If the media object is uniformly segmented, then we can determine the minimum buffer size required to avoid proxy jitter. There are three ranges which we are interested in. The first segment, the second segment and the segment upto the ratio Bs/Bt and the segments thereafter will have same minimum buffer size but they may or may not be able to avoid proxy jitter. The threshold for the number of segments we need to prefetch is Bs/Bt.
For a requested media object, if there are n segments cached in the proxy, then the objective is to schedule the prefetching of the n+1 th segment so that proxy jitter is avoided. At position x, the length of the to be delivered data is L-x and the Assuming Bs as the average playback rate and Bt as the average data transfer rate, we avoid proxy jitter when the time to transfer sum of all such remaining lengths L-x for each of the n segments and the n+1 segment over Bs is greater than the time for the the n+1 th segment over the average data transfer rate.
This is a way of saying that the prefetch time must not exceed the delivery time. From the equation above, the position can be varied such that the latest prefetch scheduling point is one where the arrival is just sufficient to meet demand. The buffer size would then reach minimum.
Determining the prefetching scheduling point should then be followed by a prefetching scheme and resource requirements.
If the media object is uniformly segmented, then we can determine the minimum buffer size required to avoid proxy jitter. There are three ranges which we are interested in. The first segment, the second segment and the segment upto the ratio Bs/Bt and the segments thereafter will have same minimum buffer size but they may or may not be able to avoid proxy jitter. The threshold for the number of segments we need to prefetch is Bs/Bt.
Sunday, April 5, 2015
Http(s) Video Proxy and VPN services
Video content from providers such as Netflix, Hulu or even YouTube are not available everywhere. Furthermore, we may want anonymity when viewing the video. Together they provide some challenge to us today to get high quality video streaming services with the same level of privacy as say the Tor project.
In this document, we will review some options and talk about the designs of a streaming proxy.
First of all, we should be specific about the video content. Most providers only do an IP level check to determine whether they should restrict the viewing. This can easily be tricked by one of the following methods:
1) VPN – We can easily create an IP tunnel over the internet to the domain where we can access the video content. This poses little or no risk over the internet and the quality may be as good as local given the ubiquity of such a technique in workplace.
2) Proxying – We can hide our IP address from the machine that we want to view the video content and check the same on sites that offer to look up our ip address. By doing so, we trick the providers into thinking we are local to the country where the service may be unrestricted.
However both of these are not necessarily guaranteed to be a working option in most cases for reasons such as:
1) we may not be at liberty to use the workplace VPN service to watch internet content that is not related to workplace
2) even if we do hide our IP address, most Internet service providers may have issues with such strategy or there might be already be address translations that affect our viewing.
3) They may require buffering or caching and this does not work well for live video.
4) Even proxy caching strategies such as segment based are actually partially caching video content.
5) We may still see startup latency or be required to start/stop the content again and again.
6) And then the delay by the proxy aka proxy jitter affects continuous streaming
Let us now look at some strategies to overcome this.
There are really two problems to tackle:
First, media content broken into segments requires a segment-based proxy caching strategies. Some of these strategies reduce the startup latency as seen by the client. They attempt to fix it by giving higher priority to caching the beginning segments of media objects. The other type of these strategies aim to reduce operational efficiency of the proxy by improving the byte hit ratio. The highest byte hit ratio can be assumed to be achieved when the segmentation is delayed as late as possible and till some realtime information can be collected
None of the segmentation strategies can automatically ensure continuous streaming delivery to the client. Such a proxy has to fetch and relay the uncached segments whenever necessary and if there is a delay it results in proxy jitter, something that affects the client rightaway and is very annoying.
Reducing this proxy jitter is foremost priority. This is where different pre-fetching schemes are involved. One way is to keep the pre-fetching window and fill in the missing data.
The trouble is that improving byte hit ratio and reducing proxy jitter conflict with each other. Proxy jitter occurs if the prefetching of uncached segments is delayed. Aggressive prefetching on the other hand reduces proxy efficiency. Prefetched segments may even be thrown away. That is why there is a tendency to prefetch uncached segments as late as possible. Secondly, the improvement in byte hit ratio also conflicts with reducing the delayed startup ratio.
Chen,Wee and Zhang in their paper “designs of high quality streaming proxy systems” discuss an active prefetching technique that they use to solve proxy jitter. And they also improve the lazy segmentation scheme which addresses the conflicts between startup latency and byte hit ratio.
#codingexercise
GetAllNumberRangeProductCubeRootPowerFourteen) (Double [] A)
{
if (A == null) return 0;
Return A.AllNumberRangeProductCubeRootPowerFourteen();
}
#codingexercise
GetAllNumberRangeProductCubeRootPowerFourteen) (Double [] A)
{
if (A == null) return 0;
Return A.AllNumberRangeProductCubeRootPowerFourteen();
}
Saturday, April 4, 2015
Today we start to wrap up reading the WRL research report on Swift Java compiler. We were discussing the results of the performance studies specifically from global CSE, Class Hierarchy analysis, method inlining, method splitting, field analysis. etc. and we were looking at those that dominated across most applications as well as those that helped in specific cases.
We now look at related work specifically comparing it to say Marmot which is a research compiler from Microsoft, BulletTrain which is a commercial compiler, HotSpot another commercial compiler - this one from Sun, TurboJ that uses a different language, Diwan, Cytron and others.
Marmot does a form of Class hierarchy analysis but has little intra procedural analysis, code motion and does not do instruction scheduling Moreover its IR is not SSA based as is the case with Swift. This is a significant difference and we consequently rule out other such compilers such as Jalapeño.
BulletTrain uses SSA for its IR and even does check elimination, loop unrolling, type propagation and method inlining HotSpot dynamically compiles code that is frequently executed and can use runtime profiling information. It also does method inning based on CHA. TurboJ translates to C for compilation by a C compiler and can do method resolution, inlining, CSE and code motion during the translation.
Marmot keeps memory operations in order except for promoting loads out of loops. Jalapeño builds an instruction level dependence graph that is not available until later. Diwan uses type based alias analysis but does not incorporate the results into the SSA. Cytron represents alias information in an SSA graph by explicitly inserting calls that may modify values if the associated operation may modify the value. The difference between this strategy and Swift's strategy is that Cytron can greatly increase the size of the SSA graph where as Swift not only enforces strict memory ordering via the global store inputs but also relax dependences where it can be proved that there are no aliases.
Diwan uses a form of aggregate analysis to detect when a polymorphic data structure is used in only one way. For example, it can show that a linked list of general objects may in fact be objects of a certain class or its subclasses. Swifts field analysis is more comprehensive and determines the exact types. Dolby and Chien describe an object inlining optimization for C++ programs that does context sensitive intra procedural analysis but it takes minutes as compared to seconds that Swift takes. Moreover Swift allows objects to be inlined even when there is no local reference. This is usually referred to as unboxing and exists for functional languages. Lastly, Swift has exploited field properties to do more escape analysis than others. In a way Swift claims to be considered as a complete compiler.
We will close this study of the WRL research report on Swift Java compiler with the conclusion section from the paper next.
#codingexercise
GetAllNumberRangeProductCubeRootPowerTwelve) (Double [] A)
{
if (A == null) return 0;
Return A.AllNumberRangeProductCubeRootPowerTwelve();
}
As we have seen, Swift IR simplified many aspects of the compiler, the use of SSA form made it easy to express optimizations. The Swift IR includes machine dependent operations and this allows all passes to operate directly on the SSA form. The manipulation operations on the SSA graph and CFG are common in all these passes.
Swift makes extensive use of interprocedural analysis. The most effective optimizations in Swift are method inlining, class hierarchy analysis, and global CSE. Swift also introduced field analysis and store resolution. Much of the overhead in Java appears to result from the object oriented style which results in greater memory latencies. There is room to improve optimizations and increase performance with such techniques as prefetching, co-locating objects or more aggressive object inlining.
We now look at related work specifically comparing it to say Marmot which is a research compiler from Microsoft, BulletTrain which is a commercial compiler, HotSpot another commercial compiler - this one from Sun, TurboJ that uses a different language, Diwan, Cytron and others.
Marmot does a form of Class hierarchy analysis but has little intra procedural analysis, code motion and does not do instruction scheduling Moreover its IR is not SSA based as is the case with Swift. This is a significant difference and we consequently rule out other such compilers such as Jalapeño.
BulletTrain uses SSA for its IR and even does check elimination, loop unrolling, type propagation and method inlining HotSpot dynamically compiles code that is frequently executed and can use runtime profiling information. It also does method inning based on CHA. TurboJ translates to C for compilation by a C compiler and can do method resolution, inlining, CSE and code motion during the translation.
Marmot keeps memory operations in order except for promoting loads out of loops. Jalapeño builds an instruction level dependence graph that is not available until later. Diwan uses type based alias analysis but does not incorporate the results into the SSA. Cytron represents alias information in an SSA graph by explicitly inserting calls that may modify values if the associated operation may modify the value. The difference between this strategy and Swift's strategy is that Cytron can greatly increase the size of the SSA graph where as Swift not only enforces strict memory ordering via the global store inputs but also relax dependences where it can be proved that there are no aliases.
Diwan uses a form of aggregate analysis to detect when a polymorphic data structure is used in only one way. For example, it can show that a linked list of general objects may in fact be objects of a certain class or its subclasses. Swifts field analysis is more comprehensive and determines the exact types. Dolby and Chien describe an object inlining optimization for C++ programs that does context sensitive intra procedural analysis but it takes minutes as compared to seconds that Swift takes. Moreover Swift allows objects to be inlined even when there is no local reference. This is usually referred to as unboxing and exists for functional languages. Lastly, Swift has exploited field properties to do more escape analysis than others. In a way Swift claims to be considered as a complete compiler.
We will close this study of the WRL research report on Swift Java compiler with the conclusion section from the paper next.
#codingexercise
GetAllNumberRangeProductCubeRootPowerTwelve) (Double [] A)
{
if (A == null) return 0;
Return A.AllNumberRangeProductCubeRootPowerTwelve();
}
As we have seen, Swift IR simplified many aspects of the compiler, the use of SSA form made it easy to express optimizations. The Swift IR includes machine dependent operations and this allows all passes to operate directly on the SSA form. The manipulation operations on the SSA graph and CFG are common in all these passes.
Swift makes extensive use of interprocedural analysis. The most effective optimizations in Swift are method inlining, class hierarchy analysis, and global CSE. Swift also introduced field analysis and store resolution. Much of the overhead in Java appears to result from the object oriented style which results in greater memory latencies. There is room to improve optimizations and increase performance with such techniques as prefetching, co-locating objects or more aggressive object inlining.
Friday, April 3, 2015
Today we continue reading the WRL research report on Swift Java compiler. We were discussing the results of the performance studies specifically from global CSE, Class Hierarchy analysis, method inlining, method splitting, field analysis. etc. We discussed how stack allocation and synchronization removal could matter on a case by case basis. Today we continue to discuss storage resolution Programs such as compress and mtrt have important loops where memory operations and runtime checks are optimized only when memory dependences are relaxed. In the case of compress program, sign extension elimination is effective because this program does many memory accesses to byte arrays. Branch removal is especially effective in one program because it made heavy use of a method that involved the computation of a boolean.
A study was made to count the number of null checks and bound checks executed in each application The count was made with all optimizations except CSE, check eliminations, field analysis and loop peeling and then counts were made with each of them successfully added. It was found the CSE is highly effective in eliminating null checks but does not eliminate any bound checks. Similarly, loop peeling eliminates a large number of null checks in several optimizations but does not remove bound checks. This is because bounds checks are not typically loop invariant.
In order to find the max benefit which is the cost of runtime checks that Swift could not eliminate, all runtime checks were removed with the possible loss of correctness, a comparison was made between full optimizations and replacement of remaining run-time checks with pin operations. The pin operations are moved upwards as much as possible without going past a branch or memory store operation It was found that these remaining runtime checks that Swift could not eliminate cost about 10-15%.
The effects of several optimizations on the number of virtual method and interface calls were also studied. A plot was drawn on the number of total unresolved calls when only virtual calls to private or to final methods were resolved. This was repeated by success fully adding resolutions from type propagation, CHA, field analysis and method return values. Again it was clear that the CHA had the most impact In one case, the return value resolved calls and improved the performance of that program.
Type propagation, field analysis and method return values have small impact compared to CA
A study was made to count the number of null checks and bound checks executed in each application The count was made with all optimizations except CSE, check eliminations, field analysis and loop peeling and then counts were made with each of them successfully added. It was found the CSE is highly effective in eliminating null checks but does not eliminate any bound checks. Similarly, loop peeling eliminates a large number of null checks in several optimizations but does not remove bound checks. This is because bounds checks are not typically loop invariant.
In order to find the max benefit which is the cost of runtime checks that Swift could not eliminate, all runtime checks were removed with the possible loss of correctness, a comparison was made between full optimizations and replacement of remaining run-time checks with pin operations. The pin operations are moved upwards as much as possible without going past a branch or memory store operation It was found that these remaining runtime checks that Swift could not eliminate cost about 10-15%.
The effects of several optimizations on the number of virtual method and interface calls were also studied. A plot was drawn on the number of total unresolved calls when only virtual calls to private or to final methods were resolved. This was repeated by success fully adding resolutions from type propagation, CHA, field analysis and method return values. Again it was clear that the CHA had the most impact In one case, the return value resolved calls and improved the performance of that program.
Type propagation, field analysis and method return values have small impact compared to CA
Subscribe to:
Posts (Atom)