Chương 7,8: Các thuật toán trong tầng mạng

Câu 26 (2 điểm): Trình bày thuật toán Flooding?

Thuật toán flooding là thuật toán để phân phối vật liệu cho mỗi phần tử của một mạng kết nối. Thuật toán flooding có nguyên lý như sau:

 Mỗi nút hoạt động như một bộ truyền và nhận(0.5 điểm).

 Mỗi nút cố gắng để chuyển tiếp tất cả mỗi tin nhắn đến mỗi hoặc một trong những nút có ở cạnh nó, trừ nút nguồn(0.5 điểm).

 Kết quả là tin nhắn được truyền từ nguồn đến đích(0.5 điểm).

Thuật toán flooding phù hợp giải quyết rất nhiều trong vấn đề toán học, trong đó có giải quyết vấn đề di chuyển trong mê cung và lý thuyết đồ thị(0.5 điểm).

Câu 27 (2 điểm): Trình bày thuật toán tìm đường đi ngắn nhất?

Bài toán(1 điểm): Cho đồ thị G = (V, E) và hai đỉnh a, b. Tìm đường đi ngắn nhất (nếu có) đi từ đỉnh a đến đỉnh b trong đồ thị G.
ý nghĩa thực tế: Bài toán này giúp chúng ta chọn các hành trình tiết kiệm nhất
(quãng đường, thời gian, chi phí ...) trong giao thông, lập lịch thi công các công trình một cách tối ưu, xử lý trong truyền tin ...Thuật toán duyệt đồ thị theo chiều rộng đã cho ta lời giải của bài toán này.
Song ta có thêm thuật toán sau đây.
Thuật toán 8.1(1 điểm):
1. Lần lượt gán nhãn cho các đỉnh của đồ thị, mỗi đỉnh không quá một lần, như sau:
- Đỉnh a được gán nhãn là số 0.
- Những đỉnh kề với đỉnh a được gán số 1.
- Những đỉnh kề với đỉnh đã được gán nhãn số 1, được gán số 2.
………………………………….
- Tương tự, những đỉnh kề với đỉnh đã được gán số i được gán nhãn là số
i+1.
………………………………….
Thực hiện cho đến khi gán được nhãn cho đỉnh b hoặc không gán nhãn
được nữa.
2. Nếu đỉnh b được gán nhãn nào đó là k thì kết luận có đường đi ngắn nhất từ đỉnh a tới đỉnh b với độ dài k, ngược lại thì trả lời là không có.
3. Khôi phục đường đi: Nếu ở bước 2. chỉ ra b được gán nhãn k nào đó thì ta đi ngược lại theo quy tắc sau đây: Nếu đỉnh y được gán nhãn j với j ≥ 1 thì sẽ có đỉnh x được gãn nhãn j-1 sao cho có cạnh đi từ x tới y. Đi ngược lại cho đến khi gặp đỉnh a, ta nhận được đường đi ngắn nhất cần tìm.

Câu 28 (2 điểm) Trình bày thuật toán vector khoảng cách?
 Thuật toán gồm các bước sau:

1. Mỗi nút tính khoảng cách giữa nó và tất cả các nút khác trong hệ thống tự chủ và lưu trữ thông tin này trong một bảng(0.5 điểm)
2. Mỗi nút gửi bảng thông tin của mình cho tất cả các nút lân cận(0.5 điểm).
3. Khi một nút nhận được các bảng thông tin từ các nút lân cận, nó tính các tuyến đường ngắn nhất tới tất cả các nút khác và cập nhật bảng thông tin của chính mình(1 điểm).
Mỗi nút thiết lập một mảng một chiều (vector) chứa khoảng cách từ nó đến tất cả các nút còn lại và sau đó phát vector này đến tất cả các nút lân cận của nó.

Câu 29* (5 điểm): Phân tích các nguyên nhân gây tắc nghẽn mạng?

Nguyên nhân của xảy ra tắc nghẽn trong môi trường mạng mới đó là :
1. Tràn bộ đệm: đây cũng là nguyên nhân giống như trong mạng truyền thống(1điểm).
2. Lỗi do đường truyền vô tuyến: các hiệu ứng môi trường như di động, che chắn, pha đinh, … gây ra mất gói và ảnh hưởng đến tắc nghẽn mạng(1điểm).
3. Do nghẽn cổ chai: tại điểm đấu nối từ các mạng tốc độ thấp vào mạng tốc độ cao. Đây là một trong những đặc điểm nổi bật của môi trường hỗn tạp(1điểm)
4. Nhu cầu băng thông cao của các dịch vụ đa phương tiện và các loại hình dịch vụ mới: dữ liệu, âm thanh và hình ảnh được tích hợp truyền trên mạng duy nhất NGN ALL – IP gây ra tắc nghẽn tại các đường truyền dẫn băng thông nhỏ(1điểm).
5. Lưu lượng lớn, thay đổi đột biến và biến đổi động: Thông thường, các ứng dụng mới trong mạng NGN được thiết kế với nhu cầu lưu lượng truyền tải lớn (đặc biệt là các ứng dụng liên quan đến cơ sở dữ liệu phân tán, hay VoIP, Video, IPTV,…). Mặt khác, những ứng dụng đa phương tiện có đặc điểm là lưu lượng biến đổi động khó dự đoán trước được(0.5điểm).
6. Tính biến động của mạng, hình trạng mạng: Đây là một đặc tính mới của mạng NGN so với mạng truyền thống. Các nút mạng có thể dịch chuyển làm hình trạng mạng thay đổi gây ra những biến đổi vềphân chia lưu lượng trên mạng(0.5điểm).

Câu 30** (3 điểm): Phân tích thuật toán loại bỏ gói tin?
Firewall hoạt động chặt chẽ với giao thức TCP/IP, vì giao thức này làm việc theo thuật tón chia nhỏ các dữ liệu nhận được từ các ứng dụng trên mạng, hay nói chính xác hơn là các dịch vụ chạy trên các giao thức (Telnet, SMTP, DNS, SMNP, NFS …) thành các gói dữ liệu (data packets) rồi gán cho các packet này những địa chỉ có thể nhận dạng, tái lập lại ở đích cần gửi đến, do đó các loại Firewall cũng liên quan rất nhiều đến các packet và những con số địa chỉ của chúng(1 điểm).
Bộ lọc packet cho phép hay từ chối mỗi packet mà nó nhận được. Nó kiểm tra toàn bộ đoạn dữ liệu để quyết định xem đoạn dữ liệu đó có thỏa mãn một trong số các luật lệ của lọc packet hay không. Các luật lệ lọc packet này là dựa trên các thông tin ở đầu mỗi packet (header), dùng để cho phép truyền các packet đó ở trên mạng. Bao gồm(1 điểm):
• Địa chỉ IP nơi xuất phát (Source)
• Địa chỉ IP nơi nhận ( Destination)
• Những thủ tục truyền tin (TCP, UDP, ICMP, IP tunnel …)
• Cổng TCP/UDP nơi xuất phát
• Cổng TCP/UDP nơi nhận
• Dạng thông báo ICMP
• Giao diện packet đến
• Giao diện packet đi
Nếu packet thỏa các luật lệ đã được thiết lập trước của Firewall thì packet đó được chuyển qua, nếu không thỏa thì sẽ bị loại bỏ. Việc kiểm soát các cổng làm cho Firewall có khả năng chỉ cho phép một số loại kết nối nhất định được phép mới vào được hệ thống mạng cục bộ. Cũng nên lưu ý là do việc kiểm tra dựa trên header của các packet nên bộ lọc không kiểm soát được nội dụng thông tin của packet. Các packet chuyển qua vẫn có thể mang theo những hành động với ý đồ ăn cắp thông tin hay phá hoại của kẻ xấu. Trong các phần sau chúng ta sẽ cùng tìm hiểu các kỹ thuật để vượt tường lửa.
Firewall trong các mô hình mạng OSI và TCP/IP Firewall hoạt động ở các lớp khác nhau sử dụng các chuẩn khác nhau để hạn chế lưu lượng. Lớp thấp nhất mà firewall hoạt động là lớp 3. Trong mô hình OSI đây là lớp mạng. Trong mô hình TCP/IP đây là lớp IP (Internet Protocol). Lớp này có liên quan tới việc định tuyến các gói tới đích của chúng. Ở lớp này, một firewall có thể xác định rằng một gói từ một nguồn đáng tin cậy, nhưng không xác định gói chứa những gì. Ở lớp transport, firewall biết một ít thông tin về gói và có thể cho phép hoặc từ chối truy cập dựa vào các tiêu chuẩn. Ở lớp ứng dụng, firewall biết nhiều về những gì đang diễn ra và có sự lựa chọn trong việc gán quyền truy cập.
IP spoofing (sự giả mạo IP) (0.5 điểm)
Nhiều firewall nghiên cứu các địa chỉ IP nguồn của các gói để xác nhận nếu chúng hợp lý. Một firewall có thể cho phép luồng lưu thông nếu nó đến từ một host đáng tin cậy. Một cracker giả mạo địa chỉ IP nguồn của các gói gửi tới firewall. Nếu firewall nghĩ rằng các gói đến từ một host tin cậy, nó có thể cho chúng đi qua trừ khi một vài chuẩn khác không thỏa. Tất nhiên cracker muốn tìm hiểu về luật của firewall để khai thác vào điểm yếu này.
Một biện pháp hiệu quả chống lại sự giả mạo IP là việc sử dụng giao thức mạng riêng ảo (Virtual Private Network - VPN) như là IPSec. Biện pháp này đòi hỏi việc mã hóa dữ liệu trong các gói cũng như địa chỉ nguồn. Phần mềm hoặc phần sụn VPN giải mã gói và địa chỉ nguồn để tiến hành một cuộc kiểm tra (checksum). Nếu cả dữ liệu lẫn địa chỉ nguồn đã bị giả mạo thì gói sẽ bị hủy.
IPSec(0.5 điểm)
IPSec có vai trò rất quan trọng trong việc giải quyết các vấn đề mà chúng ta cố giải quyết nó với firewall. IPSec (IP Security) đề ra một tập các chuẩn được phát triển bởi Internet Engineering Tast Force (IETF). IPSec giải quyết hai vấn đề gây hại cho bộ giao thức IP: Sự xác thực host-to-host (cho các host biết là chúng đang nói chuyện với nhau mà không phải là sự giả mạo) và việc mã hóa (ngăn chặn những kẻ tấn công xem dữ liệu trong luồng lưu lượng giữa hai máy). Đây là các vấn đề mà firewall cần giải quyết. Mặc dù firewall có thể làm giảm nguy cơ tấn công trên Internet mà không cần sự xác thực và mã hóa, nhưng vẫn còn hai vấn đề lớn ở đây: tính toàn vẹn và sự riêng tư của thông tin đang truyền giữa hai host và sự giới hạn trong việc đặt ra các loại kết nối giữa các mạng khác nhau. IPSec giúp giải quyết các vấn đề này.
Có vài khả năng đặc biệt khi chúng ta xem xét sự kết hợp giữa các firewall với các host cho phép IPSec. Cụ thể là, VPN, việc lọc gói tốt hơn (lọc những gói mà có tiêu đề xác thực IPSec), và các firewall lớp ứng dụng sẽ cung cấp sự xác minh host tốt hơn bằng cách sử dụng tiêu đề xác thực IPSec thay cho “just trusting.