Haste: Practical Online Network Coding in a Multicast Switch鏄垜澶т笁鏆戝亣鏃跺畬鎴愮殑璁烘枃锛岃IEEE INFOCOM 2010鎺ュ彈銆傝鏂囧叏鏂囦互鍙妔lides鍙互鍦ㄦ垜鐨勪富椤礹omepage.fudan.edu.cn/~syang涓婃壘鍒般€?/p>

杩欑瘒璁烘枃浠嬬粛浜嗗浣曞湪浜ゆ崲鏈轰笂浣跨敤缃戠粶缂栫爜鎻愰珮缁勬挱鐨勫悶鍚愮巼銆傚悓鏃讹紝璇ユ枃鎽掑純浜嗕紶缁熺殑闅忔満绾挎€х紪鐮佽€岀粰鍑轰簡鍙娇鐢ㄥ紓鎴栬繍绠楃殑Haste绠楁硶锛屽皢瑙ｇ爜寤惰繜浠嶰(N)闄嶄綆鍒颁簡0锛屽悓鏃跺皢瑙ｇ爜澶嶆潅搴︿粠O(N²)/鍖呴檷浣庡埌浜哋(1)銆傛渶鍚庤鏂囧睍绀轰簡涓€涓‖浠朵豢鐪熷钩鍙帮紝鑳藉鍦ㄤ竴鍙癙C鏈轰笂妯℃嫙浜ゆ崲鏈哄鐞嗙湡瀹炵殑UDP鏁版嵁鍖咃紝骞惰兘杩涜涓嶇紪鐮佽皟搴︼紝闅忔満绾挎€х爜鎴栬€匟aste绠楁硶銆傚叾浠跨湡缁撴灉琛ㄦ槑浣跨敤Haste鑳藉鏈夋晥鎻愰珮浜ゆ崲鏈虹殑鍚炲悙鐜囥€?/p>

涓嬮潰缁欏嚭涓€涓畝鍗曠殑渚嬪瓙浠嬬粛缃戠粶缂栫爜濡備綍鎻愰珮浜ゆ崲鏈哄悶鍚愮巼銆?/p>

涓婂浘鏄竴涓敮鎸佸鎾殑浜ゆ崲鏈虹殑浠嬬粛銆備竴涓暟鎹寘鍙互鍚屾椂琚涓緭鍑虹鍙ｆ帴鍙椼€?/p>

浣嗘槸涓€涓緭鍏ョ鍙ｄ笉鑳藉悓鏃跺彂閫佷袱涓笉鍚岀殑鏁版嵁鍖?/p>

涓€涓緭鍑虹鍙ｄ篃涓嶈兘鍚屾椂鎺ュ彈涓や釜涓嶅悓鐨勬暟鎹寘銆?/p>

鏈変簡浠ヤ笂杩欎簺闄愬埗锛屾垜浠€冭檻涓嬪浘杩欐牱鐨勬暟鎹寘浼犺緭銆傝摑鑹插拰榛勮壊鐨勬暟鎹寘浠庤緭鍏?鍙戦€佸埌鎵€鏈夎緭鍑虹鍙ｃ€傜孩鑹诧紝榛戣壊锛岀伆鑹叉暟鎹寘浠庤緭鍏ョ鍙?鍒嗗埆鍒拌緭鍑虹鍙?锛?锛?銆傝繖鏍峰嚑涓暟鎹寘鑻ヤ笉浣跨敤缃戠粶缂栫爜锛岄渶瑕?涓椂闂村崟浣嶆墠鑳藉畬鎴愩€?br />

浣嗘槸鎴戜滑鍙互浠ょ豢鑹茬瓑浜庨粍鑹?钃濊壊锛屽涓嬪浘鎵€绀恒€?/p>

杈撳嚭绔彛1鍙互閫氳繃缁胯壊鍑忓幓榛勮壊鑾峰緱钃濊壊锛岃緭鍑虹鍙?鍙互閫氳繃缁胯壊鍑忓幓钃濊壊鑾峰緱榛勮壊銆傝繖鏍蜂竴鏉ワ紝杩欐牱鍑犱釜鏁版嵁鍖呭氨鑳藉湪3涓椂闂村崟浣嶅唴瀹屾垚浼犺緭浜嗐€?/p>

瀵逛簬鏇村ぇ瑙勬ā鐨勪氦鎹㈡満锛屼紶缁熺殑缃戠粶缂栫爜閲囧彇鐨勬槸闅忔満绾挎€х爜锛屽嵆浠_i = C_i1P₁ + C_i2P₂ + C_i3P₃ + ... + C_inP_n銆傚叾涓璓鏄暟鎹寘锛孋鏄殢鏈洪€夊彇鐨勭郴鏁帮紝E鏄紪鐮佸悗鐨勬暟鎹寘銆傝繖鏍凤紝鏀堕泦榻恘涓嚎鎬ф棤鍏崇殑缂栫爜鍚庣殑鏁版嵁鍖咃紝灏卞彲浠ラ€氳繃瑙ｆ柟绋嬬殑褰㈠紡璁＄畻鍑哄師鏉ョ殑鏁版嵁鍖呫€傝繖鏍峰仛鐨勪竴涓嚧鍛界己鐐规槸瑙ｆ柟绋嬬殑澶嶆潅搴﹀緢澶э紝骞朵笖鍦ㄦ敹榻愮n涓寘涔嬪墠锛屽墠闈 - 1涓暟鎹寘閮芥槸鏃犵敤鐨勶紝浼氶€犳垚杈冨ぇ鐨勫欢杩熴€?/p>

Haste鐨勭壒鐐规槸閲囩敤浜嗘満浼氱紪鐮侊紝鍏朵粎浣跨敤寮傛垨杩愮畻銆傜紪鐮佺殑鏁版嵁涓篹 = P1 xor P2 xor P5 xor P7, 濡傛灉涓€涓緭鍑虹鍙ｅ凡瑙ｅ嚭P1, P5, P7锛岄偅涔圥2 = e xor P1 xor P5 xor P7銆傛垜浠€氳繃涓€绉嶉殢鏈虹殑椤哄簭鏉ラ€夊彇鏁版嵁鍖咃紝鍋囪闅忔満鍚庣殑椤哄簭涓篜i1, Pi2, Pi3.. Pin銆傞鍏堜护e = Pi1銆傜劧鍚庢垜浠繘琛屽惊鐜痡锛岃嫢e xor Pij鑳藉琚墍鏈夌殑杈撳嚭绔彛瑙ｇ爜锛坕.e. p1 xor p2 xor p3鑳藉琚В鐮佸綋涓斾粎褰撹绔彛鑷冲皯鏀跺埌p1,p2,p3涓殑涓や釜锛夛紝閭ｄ箞浠 = e xor Pij銆傝繖鏍凤紝鎴戜滑淇濊瘉鎵€鏈夌殑鏁版嵁鍖呴兘鏄兘澶熻绔嬪嵆瑙ｇ爜鐨勩€傚叧浜庤绠楁硶鐨勫垎鏋愬拰杩涗竴姝ヤ紭鍖栧彲浠ュ弬鑰冭鏂囥€?/p>

涓嬮潰杩欎釜鍥惧睍绀轰簡鍦ㄧ‖浠朵豢鐪熷钩鍙颁笅娴嬭瘯鐨勫悶鍚愮巼鐨勭粨鏋滐紙鏇村瀹為獙缁撴灉鍙互鍙傝€冭鏂囷級銆備紶缁熺殑缃戠粶缂栫爜鎬ц兘鏈夋墍涓嬮檷锛岃繖鏄洜涓轰娇鐢ㄨ蒋浠跺疄鐜颁紶缁熺綉缁滅紪鐮佹湁宸ㄥぇ鐨勮绠楅噺锛屽疄楠岀殑CPU涓嶈兘鎵垮彈銆備簨瀹炰笂锛屾渶鏂扮殑浣跨敤GPU杩涜闅忔満绾挎€х綉缁滅紪鐮佷篃浠呰兘瀹炵幇涓嶅埌300MBps鐨勫悶鍚愮巼锛岃€屼氦鎹㈡満鐨勫悶鍚愮巼閮芥槸涓奊鐨勩€侶aste锛岀敱浜庡叾杞婚噺鐨勮绠楀鏉傚害锛圤锛?锛?鍖咃級锛岃兘澶熷疄闄呭湴杩愮敤鍦ㄤ氦鎹㈡満涓娿€?br />
濡傛灉瀵硅璁烘枃鏈変粈涔堜笉鏄庣櫧鐨勶紝鎴栬€呮湁杩涗竴姝ョ殑寤鸿锛屾杩庝笌鎴戣仈绯汇€?br />