Task Allocation And Scheduling On Heterogeneous Multi-core Systems

The origin of the modern Internet can be traced back to the end of the 60 century,it has exceeded its original intention,and exposed more and more limitations in terms of scalabil-ity,security and mobility after nearly half a century of rapid development.In view of this,some new network structure have been proposed,such as software defined network(SDN)/network function Virtualization(NFV)and named data network(NDN),etc..Regardless of the evolution of the network structure,data packet forwarding is a core module.Among the packet forwarding researches,the forwarding table compression and the acceleration of lookup has always been a hot research topic and the forwarding table compression technol-ogy is of great importance,because it not only directly determine the network infrastructure hardware costs,but also affect the performance of the lookup to a certain extent.In this paper,we aim at the two new application scenarios of NFV and NDN,mainly study the forwarding table compression based on the merging and splitting technology.Virtual router is not only the infrastructure to realize the network function virtualiza-tion,but also a kind of practice of the core idea.this paper starts from the table merging,expanse the prefix by different identification string to distinguish the same prefix in differ-ent tables,then merge the multiple forwarding tables into a large table.In order to achieve compression,we then use the prefix splitting method to split the large table into two small tables.Finally,we focus on the storage cost rule with different split positions,further pro-poses a fast reconstruction mechanism,which obtain high storage efficiency,low overhead and can control the maintenance cost.Experimental results show that the scheme can sup-port 90,000,000 prefixes and 65600 forwarding tables,and has good scalability.When forwarding number increased from 128 to 244,FIB prefix number of entries which changes from 3,143,411 to 8,595,010,our fast system reconfiguration mechanism only need 0.329M storage space,and the original scheme need 0.867M.In addition,in comparison with the table fusion scheme of the 2-3 tree,the storage efficiency is improved by 64%.The packet forwarding of named data network involves two kind of packets,three name table and a more complicated process.Moerever,the names have more entries,no length limit,and the composition is complicated.As a result,the challenges of maintaining the name table storage has been exacerbated.The existing scheme is mainly aimed at the characteristics of one table,and is difficult to be applied to other.The use of Hash table with Bloom filter to compress the storage of a unified index table,although offers a high memory efficiency,but the effect is not stable because of the characteristics of the data and the impact of the choice of Hash function.In this paper,we aim at the association of the three tables in the forwarding process to merge the three tables into one big table,and then use the splitting scheme based on the component prefix to achieve storage compression.At the same time,we make the optimal proposal to choose the best split position based on statistical analysis of a large number of real data of the network domain name.The experimental results show that with the increasing size of the data,the proposed scheme can obtain the increase of storage efficiency by nearly 50%.