Browsing by Author "Zhang, Qin"

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    A Concise Forwarding Information Base for Scalable and Fast Name Lookups
    (IEEE, 2017-11-30) Yu, Ye; Belazzougui, Djamal; Qian, Chen; Zhang, Qin
    Forwarding information base (FIB) scalability and its lookup speed are fundamental problems of numerous net- work technologies that uses location-independent network names. In this paper we present a new network algorithm, Othello Hashing, and its application of a FIB design called Concise, which uses very little memory to support ultra-fast lookups of network names. Othello Hashing and Concise make use of minimal perfect hashing and relies on the programmable network framework to support dynamic updates. Our conceptual contribution of Concise is to optimize the memory efficiency and query speed in the data plane and move the relatively complex construction and update components to the resource- rich control plane. We implemented Concise on three platforms. Experimental results show that Concise uses significantly smaller memory to achieve much faster query speed compared to existing solutions of network name lookups.
  • Thumbnail Image
    Item
    Edit Distance: Sketching, Streaming, and Document Exchange
    (IEEE, 2016-12-19) Belazzougui, Djamal; Zhang, Qin
    We show that in the document exchange problem, where Alice holds x ∈ {0, 1}^n and Bob holds y ∈ {0, 1}^n , Alice can send Bob a message of size O(K(log^2 K + log n)) bits such that Bob can recover x using the message and his input y if the edit distance between x and y is no more than K, and output “error” otherwise. Both the encoding and decoding can be done in time O~(n+poly(K)). This result significantly improves on the previous communication bounds under polynomial encoding/decoding time. We also show that in the referee model, where Alice and Bob hold x and y respectively, they can compute sketches of x and y of sizes poly(K log n) bits (the encoding), and send to the referee, who can then compute the edit distance between x and y together with all the edit operations if the edit distance is no more than K, and output “error” otherwise (the decoding). To the best of our knowledge, this is the first result for sketching edit distance using poly(K log n) bits. Moreover, the encoding phase of our sketching algorithm can be performed by scanning the input string in one pass. Thus our sketching algorithm also implies the first streaming algorithm for computing edit distance and all the edits exactly using poly(K log n) bits of space.
  • Thumbnail Image
    Item
    Memory-Efficient and Ultra-Fast Network Lookup and Forwarding Using Othello Hashing
    (IEEE, 2018-04-11) Yu, Ye; Belazzougui, Djamal; Qian, Chen; Zhang, Qin
    Abstract: Network algorithms always prefer low memory cost and fast packet processing speed. Forwarding information base (FIB), as a typical network processing component, requires a scalable and memory-efficient algorithm to support fast lookups. In this paper, we present a new network algorithm, Othello hashing, and its application of a FIB design called concise, which uses very little memory to support ultra-fast lookups of network names. Othello hashing and concise make use of minimal perfect hashing and relies on the programmable network framework to support dynamic updates. Our conceptual contribution of concise is to optimize the memory efficiency and query speed in the data plane and move the relatively complex construction and update components to the resource-rich control plane. We implemented concise on three platforms. Experimental results show that concise uses significantly smaller memory to achieve much faster query speed compared to existing solutions of network name lookups.