资源描述:
《Network_coding_for_distributed_storage_systems》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、1NetworkCodingforDistributedStorageSystemsAlexandrosG.Dimakis,P.BrightenGodfrey,YunnanWu,MartinO.WainwrightandKannanRamchandranDepartmentofElectricalEngineeringandComputerScience,UniversityofCalifornia,Berkeley,CA94704.Email:{adim,pbg,wainwrig,kannan
2、r}@eecs.berkeley.eduandyunnanwu@microsoft.comAbstractDistributedstoragesystemsprovidereliableaccesstodatathroughredundancyspreadoverindividuallyunreliablenodes.Applicationscenariosincludedatacenters,peer-to-peerstoragesystems,andstorageinwirelessnetw
3、orks.Storingdatausinganerasurecode,infragmentsspreadacrossnodes,requireslessredundancythansimplereplicationforthesamelevelofreliability.However,sincefragmentsmustbeperiodicallyreplacedasnodesfail,akeyquestionishowtogenerateencodedfragmentsinadistribu
4、tedwaywhiletransferringaslittledataaspossibleacrossthenetwork.Foranerasurecodedsystem,acommonpracticetorepairfromanodefailureisforanewnodetodownloadsubsetsofdatastoredatanumberofsurvivingnodes,reconstructalostcodedblockusingthedownloadeddata,andstore
5、itatthenewnode.Weshowthatthisprocedureissub-optimal.Weintroducethenotionofregeneratingcodes,whichallowanewnodetodownloadfunctionsofthestoreddatafromthesurvivingnodes.Weshowthatregeneratingcodescansignificantlyreducetherepairbandwidth.Further,weshowtha
6、tthereisafundamentaltradeoffbetweenstorageandrepairbandwidthwhichwetheoreticallycharacterizeusingflowargumentsonanappropriatelyconstructedgraph.Byinvokingconstructiveresultsinnetworkcoding,weintroduceregeneratingcodesthatcanachieveanypointinthisoptima
7、ltradeoff.I.INTRODUCTIONThepurposeofdistributedstoragesystemsistostoredatareliablyoverlongperiodsoftimeusingadistributedcollectionofstoragenodeswhichmaybeindividuallyunreliable.Applicationsinvolvestorageinlargedatacentersandpeer-to-peerstoragesystems
8、suchasOceanStore[3],TotalRecall[4],andDHash++[5],thatusenodesacrosstheInternetfordistributedfilestorage.Inwirelesssensornetworks,obtainingreliablestorageoverunreliablemotesmightbedesirableforrobustdatarecovery[6],especiallyincatastrophicscenarios[7].I