[發(fā)明專利]用于減輕多路徑網(wǎng)絡(luò)中的散列相關(guān)性的方法

在審

• 申請?zhí)枺?/td>: 202011064670.1
• 申請日: 2020-09-30
• 公開（公告）號: CN112187659A
• 公開（公告）日: 2021-01-05
• 發(fā)明（設(shè)計）人: 王睿;賀可強;哈桑·瓦塞爾;周峻嵐;張時冬;列昂尼德·普捷夫斯基;莎萊施·博賈文卡塔克里斯南
• 申請（專利權(quán)）人: 谷歌有限責(zé)任公司
• 主分類號: H04L12/803
• 分類號: H04L12/803;H04L12/707;H04L12/743
• 代理公司: 中原信達知識產(chǎn)權(quán)代理有限責(zé)任公司 11219
• 代理人: 周亞榮;鄧聰惠

提供了用于減輕多路徑網(wǎng)絡(luò)中的散列相關(guān)性的方法。在這方面，可以在網(wǎng)絡(luò)中的第一交換機和第二交換機之間找到散列相關(guān)性。在此網(wǎng)絡(luò)中，將在第一交換機處從第一組出口端口當(dāng)中選擇第一出口端口用于轉(zhuǎn)發(fā)分組，并且將在第二交換機處從第二組出口端口當(dāng)中選擇第二出口端口用于轉(zhuǎn)發(fā)分組，其中第一組具有第一組大小而第二組具有第二組大小。在找到散列相關(guān)性時，可以選擇與第一組大小互質(zhì)的新的第二組大小，并且可以將第二組出口端口映射到具有新的第二組大小的映射組。第二交換機可以被配置成根據(jù)映射組來路由分組。

技術(shù)領(lǐng)域

本公開涉及用于減輕多路徑網(wǎng)絡(luò)中的散列相關(guān)性的方法。

背景技術(shù)

負載平衡在網(wǎng)絡(luò)操作和管理中至關(guān)重要。例如，利用等價多路徑(ECMP)路由，轉(zhuǎn)發(fā)到單個目的地的分組可以基于分組的報頭字段的散列來在多個最低成本路徑上發(fā)生，這允許使用多條路徑上的帶寬。在這樣的系統(tǒng)中，可以在多個流中轉(zhuǎn)發(fā)分組，并且可以通過把一個或多個報頭字段散列化使得每個流中的分組遵循同一路徑以避免分組重新排序來實現(xiàn)負載平衡。同樣地，除了可以為多條路徑指派不同的權(quán)重以外，加權(quán)成本多路徑(WCMP)路由也允許在多條路徑上將分組轉(zhuǎn)發(fā)到單個目的地，從而使一些路徑變得比其它路徑更可能被選擇。

基于散列的負載平衡的一個有挑戰(zhàn)性的問題是在不同路由器中重復(fù)使用相同或相關(guān)的散列函數(shù)可以引起負載不平衡。例如，當(dāng)不同的交換機重復(fù)地使用同一散列算法時，可以為去往一個目的地前綴的所有業(yè)務(wù)選擇單個鏈路，然而其它鏈路未充分利用或未使用。避免散列相關(guān)性的一個方式是對于網(wǎng)絡(luò)中的每個交換機使用不同的散列函數(shù)。然而，交換機芯片支持有限數(shù)量的散列函數(shù)。另外，使用大量散列函數(shù)的計算是不切實際的，因為它可能在高分組速率下產(chǎn)生瓶頸。減輕散列相關(guān)性的另一方式是基于每個具體交換機操縱若干散列函數(shù)以獲得更多的變化。然而，由于循環(huán)冗余校驗(CRC)的滾動性質(zhì)，或者當(dāng)為其它網(wǎng)絡(luò)管理保留隨機性時，這種操作可能不適用于奇數(shù)數(shù)量的等價路徑。向交換機芯片散列函數(shù)提供不同的種子可以減輕但無法解決散列相關(guān)性問題。減輕散列相關(guān)性的再一個方式是基于分組報頭中的生存時間(TTL)的值來選擇散列函數(shù)。然而，此方法需要更改數(shù)據(jù)平面中的分組處理流水線，并且因此可能需要硬件改變和供應(yīng)商合作。

發(fā)明內(nèi)容

本公開提供：由一個或多個處理器確定在網(wǎng)絡(luò)中的第一交換機與網(wǎng)絡(luò)中的第二交換機之間存在散列相關(guān)性，其中，將在第一交換機處從第一組出口端口當(dāng)中選擇第一出口端口用于轉(zhuǎn)發(fā)分組，將在第二交換機處從第二組出口端口當(dāng)中選擇第二出口端口用于轉(zhuǎn)發(fā)分組，并且第一組具有第一組大小而第二組具有第二組大小；在確定存在散列相關(guān)性時，由所述一個或多個處理器選擇與第一組大小互質(zhì)的新的第二組大小；由所述一個或多個處理器將第二組出口端口映射到具有新的第二組大小的映射組；以及由所述一個或多個處理器將第二交換機配置成根據(jù)映射組來路由分組。

確定存在散列相關(guān)性可以基于確定在第一交換機處應(yīng)用的第一散列函數(shù)與在第二組處應(yīng)用的第二散列函數(shù)相同，并且第二組是第一組能到達的。

第二組可以是ECMP組，并且所述新的第二組大小可以是進一步基于ECMP組的協(xié)方差滿足預(yù)定閾值來選擇的。

第二組可以是WCMP組，并且所述新的第二組大小可以是進一步基于WCMP組的K-S統(tǒng)計量滿足預(yù)定閾值來選擇的。

所述新的第二組大小可以是進一步基于滿足網(wǎng)絡(luò)中的路由表的存儲器容量來選擇的。

該方法可以進一步包括：由所述一個或多個處理器確定由第一交換機對于第一組的第一存儲器使用率大于由第二交換機對于第二組的第二存儲器使用率，其中，選擇新的第二組大小是基于第一存儲器使用率大于第二存儲器使用率。

該方法可以進一步包括：由所述一個或多個處理器確定由第一交換機對于第一組的第一存儲器使用率小于由第二交換機對于第二組的第二存儲器使用率，其中，代替選擇新的第二組大小并映射到映射組，新的第一組大小被選擇用于映射第一組。