[發明專利]基于命名數據網絡的Top-k查詢方法及系統

有效

• 申請號: 201810275795.5
• 申請日: 2018-03-30
• 公開（公告）號: CN108710629B
• 公開（公告）日: 2021-07-16
• 發明（設計）人: 廖祝華;滕增德;張健;劉毅志;易愛平
• 申請（專利權）人: 湖南科技大學
• 主分類號: G06F16/953
• 分類號: G06F16/953;G06F16/2458
• 代理公司: 湖南兆弘專利事務所(普通合伙) 43008
• 代理人: 譚武藝

本發明公開了一種基于命名數據網絡的Top?k查詢方法及系統，本發明在命名數據網絡中的數據消費節點上查詢興趣包的發送和路由轉發，在命名數據網絡中的數據生產節點上進行本地化數據Top?k查詢處理，在命名數據網絡中的路由節點上對來自不同數據源而有關同一興趣的返回數據包中各數據項的排序、聚合處理以及最終返回完備的Top?k查詢結果給上一跳，最終逐級回溯直到發出查詢興趣包的數據消費節點，進而完成整個Top?k查詢過程。本發明不僅能夠在路由過程中處理大規模數據，而且提高了查詢的效率、可擴展性和性能。

技術領域

本發明涉及命名數據網絡(NDN)來實現動態分布數據的查詢方法，具體涉及一種基于命名數據網絡的Top-k查詢方法及系統，包含數據在查詢轉發、響應處理和排序聚合及返回的各個模塊階段的實現過程。

背景技術

命名數據網絡(Named Data Networking，NDN)是一種新興的互聯網體系架構，從現在的以主機為中心的IP網絡體系結構會逐漸演變成以數據為中心的命名數據網絡體系結構。NDN可以實現命名數據在分布式網絡中基于名字的路由和轉發，而不再依賴于類似IP網絡中的地址來進行路由和轉發數據，同時它采用分層結構化命名方法對內容名稱進行命名，類似于IP地址前綴機制來迅速定位所需要的信息內容。NDN中有消費者(Consumer)和生產者(Producer)和兩種類型的傳輸包：興趣包(Interest Packet)和數據包(DataPacket)，命名數據網絡中的路由節點包含待定興趣表(PIT)、內容存儲(CS)和轉發信息庫(FIB)三個組件，其中，PIT的作用是保存興趣包發送的請求信息，以保證當接收到數據包時可以根據這些信息將其正確地返回給請求者，CS的作用類似于IP路由中的內容緩存存儲，主要作用為緩存數據以備以后查找使用，FIB是用來將興趣包發送至潛在匹配的內容數據包所在的節點，與IP路由器相比，它可以實現同時向多個節點轉發興趣包。

NDN根據名字路由和轉發包，從而消除了IP架構中地址造成的四個問題：地址空間耗盡、NAT穿越、流動性和可擴展的地址管理。NDN沒有地址枯竭的問題，因為命名空間是無限的；NDN同樣不存在穿越問題，因為一臺主機在傳送內容時并不需要暴露其地址；流動性指的是主機IP地址發生變化，但是在NDN中不再需要中斷通信，因為數據的名稱保持不變；最后，在本地網絡不再需要進行地址的分配和管理。傳統的IP網絡路由采用一個單一的最佳路徑，而命名數據網絡支持多路徑路由。

Top-k查詢在處理海量的數據時顯示出很好的查詢效率，它的基本含義為：給定N個數據項，從中選出與用戶興趣最匹配和最相關的k(k≤N)個數據項，然后采用相關的一些技術或查詢算法，將所得的數據結果返回給用戶。

但是，如何基于命名數據網絡(NDN)來實現動態分布數據的Top-k查詢，且確保該查詢方式高效可靠、響應快速，能夠解決命名數據網絡查詢中返回結果的爆炸式增長的問題，則仍然是一項亟待解決的關鍵技術問題。

發明內容

本發明要解決的技術問題：針對現有技術的上述問題，提供一種基于命名數據網絡的Top-k查詢方法及系統，本發明不僅能夠在路由過程中處理大規模數據，而且提高了查詢的效率、可擴展性和性能。

為了解決上述技術問題，本發明采用的技術方案為：

一種基于命名數據網絡的Top-k查詢方法，實施步驟包括：

1)接收上一跳的查詢興趣包，對循環或重復的查詢興趣包對應的查詢興趣包進行抑制，如果接收的查詢興趣包被抑制，則跳轉執行步驟1)；否則，跳轉執行步驟2)；

2)判斷完全匹配內容存儲CS是否找到匹配的Top-k查詢結果，如果找到匹配的Top-k查詢結果則跳轉執行步驟3)；否則，跳轉執行步驟4)；

3)判斷Top-k查詢結果是否完備，如果Top-k查詢結果完備，則向上一跳返回完備的Top-k查詢結果，結束并退出；否則如果Top-k查詢結果不完備，則跳轉執行步驟4)；