Các routers trên Internet phải xử lý cực nhiều packets với tốc độ cực cao. Giả sử ta phải thiết kế một thuật toán để chỉ ra, trong một dòng các packets đã thấy cho đến thời điểm này (n packets, và n có thể cực lớn), có source-IP nào xuất hiện hơn n/2 lần hay không. Sự xuất hiện của một source-IP như vậy có thể là dấu hiệu của DoS từ IP nọ.
Do tốc độ xử lý phải cao tuyệt, thuật toán phải chạy nhanh và không dùng quá nhiều memory được (dùng cache memory thôi). Tóm lại thuật toán chỉ có thể thực hiện một scan qua dòng packets, dùng càng ít memory càng tốt.
Cách brute-force là dùng
2^{32}
counters, mỗi counter cho một (potential) IP. Khi thấy IP mới thì tăng counter lên. Dĩ nhiên cách này không khả thi.
Hãy thiết kế một thuật toán như vậy dùng [O(log n) + 32 bit] memory, cho phép false positive nhưng không cho phép false negative. Nghĩa là thuật toán luôn output một IP address. Nếu có IP xuất hiện hơn n/2 lần thì thuật toán phải output nó. Nếu không có IP xuất hiện hơn n/2 lần thì output gì cũng được.
9 Comments
Bài này thay vì tìm IP ta tìm giá trị các bit của IP bằng cách đếm số lần xuất hiện của các bit 0, 1 tại 32 vị trí và lấy bit có số lần xuất hiện cao hơn.
Anh Hưng có cách nào scan một lần, dùng ít memory mà đảm bảo không có false positive lẫn false negative không ạ?
Hello Thang, có thể chứng minh được là cần đến linear-space nếu phải output chính xác.
Cách của Thang rất hay, nhưng cần đến 32x log(n) memory bits. Có cách nào chỉ cần log n + 32 bits of memory không?
Với cách làm của bạn Thắng, liệu có thể dùng 1 counter để lưu lại tất cả những giá trị đếm được của 32 bits không ? Em nghĩ có thể lưu lại những giá trị đếm được bằng cách biểu diễn :
n = n_{1}p_{1} + n_{2}p_{2} + \ldots + n_{32}p_{32}Trong đó
p_{i}là số nguyên tố thứ
,
n_{i}là số lần xuất hiện bit 1 tại vị trí thứ
.
Với mỗi IP trong dãy, nếu bit thứ
của IP này là 1 thì ta tăng số
lên
p_{k}đơn vị.
Hi Cường,
Biểu diễn muốn duy nhất phải là nhân chứ không phải linear combination. Ngoài ra, tổng số bits (cho dù là n có cách biểu diễn duy nhất thành linear combination của một số các số nguyên tố) cũng vẫn nhiều quá.
Oobs, em không tính kĩ memory. Em xin chỉnh lại thuật toán để giảm a few bits
Ta dùng biến 32 bits
để lưu Source IP, biến đếm log(n) bits
tại thời điểm ban đầu.
Với mỗi package, nếu
ta gán
ngược lại
. Mỗi khi
ta cập nhật giá trị mới
.
Lần trước trong blog này đã có bài đố về giọt máu gì đó rồi. Về ý tưởng cũng tương tự như bài này. Cả 2 bài cũng có một cách giải chung.
Em nghe có mùi hashing hoặc bloom filter. Không biết có đúng hướng không anh Hưng?
Hello Hoàng, nếu tổng quát hóa bài toán lên thì một biến thể của Bloom filter có thể giải quyết được. Nhưng trong trường hợp câu đố này thì cách giải thứ 2 của Thắng là chính xác.
Mình thấy bài này rất giống một bài trong sách lập trình Pascal của BTT cho học sinh cấp 3 gọi là số chính của một file.