Tài liệu định tuyến thông tin trong mạng tcpip bằng phương pháp tĩnh xây dựng monitoring để giám sát đường đi của các gói

Tiểu luận lập trình mạng Định tuyến và giám sát đường đi gói tin ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA ------ TIỂU LUẬN MÔN LẬP TRÌNH MẠNG §Ò tµi: ĐỊNH TUYẾN THÔNG TIN TRONG MẠNG TCP/IP BẰNG PHƯƠNG PHÁP TĨNH XÂY DỰNG MONITORING ĐỂ GIÁM SÁT ĐƯỜNG ĐI CỦA CÁC GÓI Giáo viên hướng dẫn: PSG. TS. Lê Văn Sơn Học viên thực hiện : Đinh Thị Mỹ Hạnh Lê Minh Trí Lớp : Cao học Máy tính_K11 ---Đà Nẵng 03/2010--- Nhóm 28 – Cao học khóa 11 Trang 1 Tiểu luận lập trình mạng Định tuyến và giám sát đường đi gói tin MỤC LỤC LỜI MỞ ĐẦU...............................................................................................................2 CHƯƠNG 1................................................................................................................... 3 NHỮNG VẤN ĐỀ CƠ BẢN CỦA VIỆC ĐIỀU KHIỂN TẢI......................................3 1. Đặt vấn đề.............................................................................................................3 2. Điều khiển tải........................................................................................................3 2.1. Điều khiển tải tổng quát..................................................................................3 2.2. Điều khiển tải phân tán...................................................................................4 2.3. Triển khai quá trình điều khiển tải...................................................................5 CHƯƠNG 2................................................................................................................... 9 ĐỊNH TUYẾN THÔNG TIN TRONG MẠNG TCP/IP................................................9 1. Tổng quan về định tuyến........................................................................................9 2. Kỹ thuật định tuyến tập trung và định tuyến phân tán............................................9 3. Kỹ thuật định tuyến thích nghi và định tuyến không thích nghi...........................10 4. Qúa trình định tuyến trong mạng TCP/IP.............................................................10 4.1. Phương pháp cố định (Fixed Routing)........................................................12 4.2. Phương pháp thích nghi/động (Adaptive Routing)........................................16 4.3. Kết luận.........................................................................................................26 CHƯƠNG 3................................................................................................................. 28 XÂY DỰNG CHƯƠNG TRÌNH MONITORING......................................................28 GIÁM SÁT ĐƯỜNG ĐI CỦA CÁC GÓI...................................................................28 THEO PHƯƠNG PHÁP ĐỊNH TUYẾN TĨNH..........................................................28 1. Mô tả bài toán......................................................................................................28 2. Xây dựng các chương trình của bài toán..............................................................29 3. Kết quả chạy thử chương trình.............................................................................29 KẾT LUẬN.................................................................................................................32 TÀI LIỆU THAM KHẢO...........................................................................................33 Nhóm 28 – Cao học khóa 11 Trang 2 Tiểu luận lập trình mạng Định tuyến và giám sát đường đi gói tin LỜI MỞ ĐẦU Với sự phát triển của khoa học và kỹ thuật, ngày nay các mạng máy tính đã phát triển một cách nhanh chóng và đa dạng cả về quy mô, hệ điều hành và ứng dụng. Khi thông tin có thể được sử dụng chung thì nó mang lại cho người sử dụng khả năng tổ chức lại các công việc với những thay đổi về chất như: - Ðáp ứng những nhu cầu của hệ thống ứng dụng kinh doanh hiện đại. - Cung cấp sự thống nhất giữa các dữ liệu. - Tăng cường năng lực xử lý nhờ kết hợp các bộ phận phân tán. - Tăng cường truy nhập tới các dịch vụ mạng khác nhau đang được cung cấp trên thế giới. Thông qua môi trường mạng, con người có thể giao tiếp với nhau và chia sẻ thông tin dữ liệu dù ở khoảng cách rất xa. Vấn đề đặt ra là làm sao phải đảm bảo dữ liệu trên mạng phải thống nhất. Đây cũng chính là một trong những yêu cầu chính của lĩnh vực Lập trình mạng. Điều khiển tải của mạng TCP/IP trong quá trình định tuyến các gói thông tin là một bài tóan lớn và phức tạp trong lĩnh vực truyền thông nói chung, vì vậy trong phạm vi của đề tài này, em xin trình bày những kết quả nghiên cứu về quá trình định tuyến trong mạng TCP/IP và xây dựng chương trình Monitoring giám sát đường đi của các gói. Tiểu luận gồm có 3 chương Chương 1: Những vấn đề cơ bản của việc điều khiển tải. Chương 2: Định tuyến thông tin trong mạng TCP/IP. Chương 3: Xây dựng chương trình Monitoring giám sát đường đi của các gói theo phương pháp định tuyến tĩnh. Cuối cùng tôi xin chân thành cảm ơn PGS. TS. Lê Văn Sơn đã trang bị kiến thức và tạo mọi điều kiện thuận lợi để tôi hoàn thành tiểu luận này. Học viên thực hiện Đinh Thị Mỹ Hạnh Lê Minh Trí Nhóm 28 – Cao học khóa 11 Trang 3 Tiểu luận lập trình mạng Định tuyến và giám sát đường đi gói tin CHƯƠNG 1 NHỮNG VẤN ĐỀ CƠ BẢN CỦA VIỆC ĐIỀU KHIỂN TẢI 1. Đặt vấn đề Việc truyền dữ liệu trong mạng phụ thuộc vào rất nhiều yếu tố, đặc biệt phụ thuộc vào khả năng và chiến lược cung cấp tài nguyên của mạng (đường truyền, bộ nhớ đệm, …). Nếu khả năng tài nguyên là có hạn (trong thực tế đây là điều thường gặp của các hệ thống) và một chiến lược cung cấp tài nguyên lại quá “tĩnh” không thích nghi với trạng thái luôn thay đổi của mạng thì rất dễ dẫn đến các tình trạng xấu sau đây:  Các yêu cầu tài nguyên dồn về một nút nào đó gây nên tình trạng “ùn tắc” do khả năng tài nguyên của nút không đáp ứng nổi  Tài nguyên của một nút nào đó có hiệu suất sử dụng quá thấp do rất ít yêu cầu được chuyển qua nó. Để tránh các tình trạng xấu trên, cần thiết phải có một cơ chế điều khiển tải thích hợp áp dụng cho toàn mạng. 2. Điều khiển tải Chức năng quan trọng nhất của việc điều khiển tải là duy trì một cách nhịp nhàng các yêu cầu về tài nguyên của hệ trong một giới hạn chấp nhận được trên cơ sở số tài nguyên hiện hành và các thông số hiệu năng cần phải tuân thủ của hệ thống. Nói một cách ngắn gọn, vai trò của điều khiển tải là làm cho việc lưu thông trên mạng tốt nhất, giảm tối đa tình trạng quá tải dẫn đến nghẽn mạng và được thể hiện dưới hai phương diện sau đây:  Điều khiển tải tổng quát: Điều khiển tải tổng quát chịu trách nhiệm giữ nhịp cho các hoạt động cung cấp tài nguyên.  Điều khiển tải phân tán: Phân tán tải cho các đối tượng có khả năng cung cấp như là người điều khiển hợp lý việc phân bố tài nguyên. 2.1. Điều khiển tải tổng quát Mục tiêu của phương pháp này là tìm cách duy trì tổng số yêu cầu tài nguyên được lưu chuyển trong mạng luôn nhỏ hơn một giá trị giới hạn (ngưỡng) N nào đó. Giá trị N sẽ được xác định trước căn cứ vào khả năng tài nguyên và cũng như kinh nghiệm hoạt động của mạng. Về mặt tổ chức, các yêu cầu về sử dụng tài nguyên được gởi đến hệ thông qua sự trung gian của một tiến trình gọi là bộ phân phối tải và được thể hiện hình H.1.1 dưới đây Nhóm 28 – Cao học khóa 11 Trang 4 Tiểu luận lập trình mạng Định tuyến và giám sát đường đi gói tin EMBED Visio.Drawing.11 Hình 1. Sơ đồ điều khiển tải tổng quát Trình tự làm việc như sau: Đầu tiên, yêu cầu tài nguyên được hình thành bởi một đề nghị phục vụ nào đó cho một Server xác định trong số các Server có khả năng phục vụ. Bộ điều khiển tải có chức năng cung cấp thông tin kịp thời và tương đối chính xác về khả năng của các Server chấp nhận hay không chấp nhận các yêu cầu. Trong khi vận hành hệ thống, bộ điều khiển tải chỉ biết được giá trị gần đúng của tải này, đó chính là nguyên nhân cơ bản của hai vấn đề khó khăn sau: STT 1 2 Thuyết minh Nếu tải vượt quá mức cho phép, bộ điều khiển tải có thể quyết định sai là ném các yêu cầu tài nguyên ra ngoài tầm phục vụ. Điều đó có thể dẫn đến việc sử dụng dưới mức giới hạn cho phép của các tài nguyên được điều khiển bởi các SERVER Nếu tài nguyên còn dưới mức cho phép, bộ điều khiển tải chấp nhận một yêu cầu; Nếu các SERVER không có sự điều khiển tải của riêng mình. Điều đó dẫn đến việc sử dụng quá mức giới hạn của các tài nguyên Cần lưu ý rằng, chức năng của các Server là đảm bảo cho hệ nói chung mỗi khi tiếp nhận các yêu cầu mới cần phải tính ngay đến việc là yêu cầu này sẽ cần phải kết thúc một cách bình thường. Phương pháp điều khiển tải tổng quát gặp khó khăn lớn nhất là phải tính tóan giá trị đáp ứng tài nguyên của mạng (Giá trị ngưỡng N) cho hợp lý. Do khả năng đáp ứng tài nguyên của mạng luôn thay đổi nên giá trị N phải được xác định lại sau một khoảng thời gian xác định để tăng tải cho mạng. Tuy nhiên để làm được việc đó thì phần mềm sẽ phức tạp hơn nhiều. Nhóm 28 – Cao học khóa 11 Trang 5 Tiểu luận lập trình mạng Định tuyến và giám sát đường đi gói tin 2.2. Điều khiển tải phân tán Phương pháp này không yêu cầu duy trì một giới hạn các yêu cầu tài nguyên chung cho mạng mà giao cho các đối tượng có khả năng cung cấp như là người điều khiển hợp lý việc phân bố các tài nguyên. Ta biết rằng để cho các Server có thể thực hiện được các yêu cầu thì việc đầu tiên là các yêu cầu này phải được dịch sang ngôn ngữ đang được sử dụng của chính Server đó. Việc phân bố tải được tiến hành sao cho các Server có khả năng phục vụ phải có tải tương đương nhau. Bộ phân phối tải được hình thành chỉ để sử dụng cho những tài nguyên phần cứng như là bộ xử lý, các thiết bị ngoại vi, đường truyền và không phải cho các tài nguyên đã được giao hẳn cho các trạm như là các tệp tin. Người ta chia ra thành hai loại chiến lược phân tán tải như sau:  Chiến lược tĩnh: việc phân tán các yêu cầu giữa các Server được xác định theo kiểu cố định, nghĩa là việc định tuyến để phân phối tải được thực hiện một lần cho toàn cuộc, không hề có sự thay đổi giữa chừng.  Chiến lược thích nghi: Việc phân tán này được xác định như là chức năng phân tán của hệ. 2.3. Triển khai quá trình điều khiển tải Trong các hệ thống phân tán, việc điều khiển tải được tiến hành ở tầng giao vận, nơi bao gồm nhiều tài nguyên phần cứng như các đường truyền thông tin hay các bộ nhớ đệm trong các nút mạng. Trong các ứng dụng khác, các trạm thông thường được chuyên môn hóa và do vậy, ta có rất ít cơ hội để thực hiện các công việc này. Để minh hoạ cho các phương pháp điều khiển tải trên đây, ta sẽ xem xét một vài ví dụ triển khai công việc điều khiển tải sau đây. 2.3.1. Ví dụ về điều khiển tải tổng quát Trong ví dụ này ta mô phỏng cho mạng máy tính quốc gia về thí nghiệm vật lý. Từ đó có thể rút ra những kinh nghiệm cần thiết cho việc triển khai bộ phân phối tải một cách hiệu quả nhất. Một vấn đề quan trọng mà ta cần quan tâm giải quyết là giới hạn các gói thông tin lưu thông trong mạng. Lưu lượng Thực tế, khi(gói/ tănggiây) số lượng các gói tin nghĩa là tăng tải cho đường truyền điều này sẽ dẫn đến lưu lượng thông tin trên đường truyền giảm mạnh rồi dừng hẳn như đồ thị sau Nhóm 28 – Cao học khóa 11 36 72 Hình 1.2: Sự quá tải trong mạng giao vận 108 góiTrang 6 Tiểu luận lập trình mạng Định tuyến và giám sát đường đi gói tin Phương pháp điều khiển này thể hiện việc duy trì số lượng toàn bộ các gói tin luân chuyển phải nhỏ hơn hay bằng một giá trị tối ưu T nào đó. Số lượng này phát huy tác dụng trong toàn bộ mạng và được gọi là cái “cho đi qua” của chính mạng đó. Một gói tin đầy đủ tham gia vào quá trình tuần hoàn cần phải là một vật mang một cái “cho đi qua” về phía đầu kia của mạng. Mỗi nút mạng được coi là một thiết bị cuối và được phép tự động lưu trữ bất kỳ từ các cái “cho đi qua” có sẵn nhằm có thể tiếp nhận các gói mới. Ta có thể so sánh hoạt động của cái “cho đi qua” với hoạt động của tập hợp xe tắc xi. Các xe rỗi ở lại trong các bến xe và chờ đến phiên mình theo một số lượng nhất định. Các xe khác di chuyển theo kiểu nối đuôi chỗ trống trong một bến khác để chờ khách. Các kết quả mô phỏng trong công trình của Price thể hiện trong hình 1.3 dưới đây. Tại đây, ta thấy rằng lợi ích cơ bản của phương pháp là giảm bớt thời gian truyền thông tin và tăng thời gian tiếp nhận thông tin Thời gian truyền (ms) Không kiểm tra 10 Thời gian truyền (ms) Có kiểm tra 10 Có kiểm tra 5 5 Tải ( gói/ giây) Không kiểm tra Tải ( gói/ giây) 3000 5000 7000 9000 3000 5000 Hình 1.3: Hiệu ứng kiểm tra trên các hành vi của việc điều khiển tải của tầng giao vận Việc kiểm tra cho thấy tính chất đặc biệt thú vị khi giảm chu chuyển các cái “cho đi qua” có sẵn khi đồ thị tăng lên. Ngược lại, nó biểu hiện một vài hạn chế:  Nếu đồ thị cũng không phân tán trong mạng, các cái “cho đi qua”có thể bị tập trung vào một vùng. Kết quả là lưu lượng vào bị chậm lại trong phần còn lại của mạng.  Thành tích của mạng phụ thuộc rất nhiều vào một số các tham số mà khó có thể xác định được giá trị tối ưu. Đó là số lượng toàn bộ các cái “cho đi qua” trong một mạng, số lượng cực đại các cái “cho đi qua” bởi một nút, kiểu phân phối lại các cái “cho đi qua” bằng số dôi ra trong một nút. Nhóm 28 – Cao học khóa 11 Trang 7 Tiểu luận lập trình mạng  Định tuyến và giám sát đường đi gói tin Các cái “cho đi qua” khi chu chuyển trong mạng có thể bị mất hay bị nhân lên. Điều đó làm thay đổi số lượng của chúng. 2.3.2. Ví dụ về điều khiển tải thích nghi Trong mạng viễn thông theo kiểu chuyển mạch gói X25, các phương pháp định tuyến thích nghi xác định con đường cho mỗi gói tin theo kiểu động dựa vào tiêu chuẩn tối ưu như độ trễ, hành trình, khoảng cách phải đi qua, sự cố đường truyền, các nút,… được xét đến. Trong mạng ARPANET, các nút đều lưu trữ bảng TD cho mỗi nút đến D và cho mỗi đường ra L. Bảng này cho biết thời hạn cần thiết để đạt đến nút D bằng cách tận dụng đường L như là giai đoạn thứ nhất. Xuất phát từ bảng này, để cho mỗi nút, ta xây dựng bảng định tuyến TR và vector thời hạn VD. Bảng này cho ta biết lần lượt các con đường cần đi qua để đến nút đích trong thời hạn ngắn nhất và giá trị cụ thể của thời hạn này. Ta ký hiệu {Dj} là tập hợp các đích của mạng ( j= 1..m) Và {Lj } là tập hợp các đường xuất phát từ nút (j= 1..n) Các bảng cần duy trì trong mỗi nút mạng như sau: TD(j,i) Thời gian để đến được nút Dj xuất phát từ đường Li TR(j) Số hiệu đường truyền tối ưu được đánh giá để đến được Dj (theo VD(j)) Hàm tối ưu VD(j) Xác định thời hạn nhỏ nhất để đến được nút Dj VD(j)= min TD(j,i) với i= 1..n Ví dụ sau đây (Hình 1.4) cho phép ta hình dung về bảng định tuyến thích nghi. Trong ví dụ này, ta sử dụng một nút có 3 đường ra (n=3) và có thể gởi tới 5 nút nhận (m=5) L1 L2 L3 TR(j) VD(j) D1 0.2 0.1 0.4 L2 0.1 D2 0.1 0.3 0.5 L1 0.1 D3 0.6 0.4 0.2 L3 0.2 D4 0.3 0.5 0.1 L3 0.1 D5 0.6 0.4 0.2 L3 0.2 Hình 1.4: Bảng định tuyến thích nghi Các bảng này được cập nhật trong hai trường hợp sau đây:  Cập nhật nội dung hàng đợi đã được phối hợp với đường ra. Mỗi khi có một gói tin được lấy ra (hay cho vào) từ hàng đợi đã được phối hợp với một đường Nhóm 28 – Cao học khóa 11 Trang 8 Tiểu luận lập trình mạng Định tuyến và giám sát đường đi gói tin truyền L, các thời hạn trong bảng, tương ứng với cột TD(j,L) cần phải được thay đổi để thích ứng với tải mới của đường truyền.  Tiếp nhận một Vector biểu hiện thời hạn được gởi đến từ nút lân cận Bây giờ, ta hãy xem xét cấu hình được thể hiện trong hình 1.5 sau đây: Hình 1.5: Mô hình định tuyến thích nghi Tại thời điểm cho trước, các nút mạng A, B, C lần lượt có các véc tơ VA, VB, VC. Véc tơ VA cung cấp thời hạn đánh giá cho các con đường AB, AC,…, AX. Theo chu kỳ cứ 2/3 giây trong mạng ARPANET mỗi nút đều tính lại véc tơ. Đó chính là thời hạn của mình và truyền giá trị đó cho các nút lân cận để cập nhật các bảng thời hạn của chúng. Ví dụ: Khi A nhận từ B và C các giá trị VB và VC, nó tính tóan lại các thời hạn để cho các đích truy cập thông qua B và C. Đó chính là thời hạn mới để cho đích X là tối thiểu của AB+BX và AC+CX Ta lưu ý rằng các thời hạn được tính tóan tương ứng với tình hình trước vài giây so với thời điểm hiện hành vì lý do cập nhật. Điều đó có thể dẫn đến sự biến động tải trong các nút. Nhóm 28 – Cao học khóa 11 Trang 9 Tiểu luận lập trình mạng Định tuyến và giám sát đường đi gói tin CHƯƠNG 2 ĐỊNH TUYẾN THÔNG TIN TRONG MẠNG TCP/IP 1. Tổng quan về định tuyến Định tuyến là sự lựa chọn một con đường để truyền một đơn vị dữ liệu (một gói tin chẳng hạn) từ trạm nguồn đến trạm đích sao cho tối ưu nhất. Do vậy, một kỹ thuật định tuyến phải thực hiện 2 chức năng sau đây:  Quyết định định tuyến theo những tiêu chuẩn tối ưu nào đó. (1)  Cập nhật thông tin định tuyến, tức là thông tin dùng cho chức năng (2) Có rất nhiều kỹ thuật định tuyến khác nhau. Sự phân biệt giữa chúng chủ yếu căn cứ vào các yếu tố liên quan đến 2 chức năng trên. Các yếu tố đó thường là: (a) Sự phân tán các chức năng định tuyến trên các nút của mạng (b) sự thích nghi với trạng thái hiện hành của mạng (c) Các tiêu chuẩn tối ưu để định tuyến Dựa trên yếu tố (a) ta có kỹ thuật định tuyến tập trung (Centralized Routing) hoặc phân tán (Distributed Routing). Dựa trên yếu tố (b) ta có kỹ thuật định tuyến tĩnh (Static hay Fixed Routing) hoặc thích nghi (Adaptatif Routing) Cuối cùng, các kỹ thuật định tuyến cùng loại (theo (a) và (b)) lại có thể phân biệt bởi yếu tố (c). Tiêu chuẩn tối ưu để định tuyến được xác định bởi người quản lý hoặc thiết kế mạng. Các tiêu chuẩn tối ưu có thể là: - Độ trễ trung bình của việc truyền gói tin - Số lượng nút trung gian giữa nguồn và đích của gói tin - Độ an toàn của việc truyền tin - Cước phí truyền tin - V.v… - Tổ hợp các tiêu chuẩn trên Việc chọn các tiêu chuẩn tối ưu như vậy phụ thuộc vào rất nhiều yếu tố của mạng như: Topo, thông lượng, mục đích sử dụng v.v… 2. Kỹ thuật định tuyến tập trung và định tuyến phân tán Kỹ thuật định tuyến tập trung được đặc trưng bởi sự tồn tại của một hoặc vài trung tâm điều khiển mạng thực hiện việc định tuyến, sau đó gởi các bảng định tuyến (Routing Table) tới tất cả các nút dọc theo con đường đã được chọn đó. Trong trường hợp này, thông tin tổng thể của mạng cần dùng cho việc định tuyến chỉ được cất giữ tại Nhóm 28 – Cao học khóa 11 Trang 10 Tiểu luận lập trình mạng Định tuyến và giám sát đường đi gói tin trung tâm điều khiển mạng. Các nút mạng có thể không gởi bất kỳ thông tin trạng thái nào của chúng tới trung tâm, hoặc gởi theo định kỳ, hoặc gởi khi có sự thay đổi nào đó. Trung tâm điều khiển sẽ cập nhật các bảng định tuyến dựa trên những thông tin nhận được từ các trạm gởi lên. Với kỹ thuật định tuyến phân tán thì không tồn tại trung tâm điều khiển mạng. Quyết định định tuyến được thực hiện tại mỗi nút của mạng. Điều này đòi hỏi sự trao đổi thông tin thường xuyên giữa các nút trong mạng. 3. Kỹ thuật định tuyến thích nghi và định tuyến không thích nghi Kỹ thuật định tuyến không thích nghi (hay còn gọi là kỹ thuật định tuyến tĩnh) có thể tập trung hoặc phân tán nhưng nó không đáp ứng với mọi sự thay đổi trên mạng. Trong trường hợp này, việc định tuyến được thực hiện mà không có sự trao đổi thông tin, không đo lường và không cập nhật thông tin. Tiêu chuẩn tối ưu để định tuyến và bản thân con đường được chọn một lần cho toàn cuộc, không hề có sự thay đổi giữa chừng. Các kỹ thuật định tuyến tĩnh rõ ràng là đơn giản, do vậy được sử dụng rộng rãi, đặc biệt trong các mạng tương đối ổn định, ít có sự thay đổi về topo và lưu thông trên mạng. Kỹ thuật định tuyến thích nghi (hay còn gọi là kỹ thuật định tuyến động) thu hút sự quan tâm đặc biệt của những nhà thiết kế mạng do khả năng đáp ứng đối với các trạng thái khác nhau của mạng. Đây là yếu tố rất quan trọng, đặc biệt là đối với các ứng dụng thời gian thực trong đó yêu cầu đầu tiên của người sử dụng là mạng phải có khả năng cung cấp được các con đường khác nhau để dự phòng sự cố và thích nghi nhanh chóng với các thay đổi trên mạng. Mức độ thích nghi của một kỹ thuật định tuyến được đặc trưng bởi sự trao đổi thông tin định tuyến trong mạng. Đơn giản nhất là không trao đổi gì hết. Mỗi nút (hoặc trung tâm điều khiển trong trường hợp kỹ thuật tập trung) hoạt động một cách độc lập với thông tin riêng của mình để thích nghi với sự thay đổi của mạng theo một phương pháp nào đó. Ở mức độ cao hơn, thông tin về trạng thái của mạng có thể được cung cấp từ các nút láng giềng hoặc từ tất cả các nút khác. Thông thường, các thông tin được đo lường và sử dụng cho việc định tuyến gồm: - Các trạng thái đường truyền - Các độ trễ truyền dẫn - Mức độ lưu thông - Các tài nguyên khả dụng - v.v… Khi có sự thay đổi trên trên mạng (ví dụ thay đổi topo do sự cố hoặc do sự phục hồi của một nút mạng, thêm nút mới, v.v…, hoặc thay đổi về mức độ lưu thông) các thông tin trên cần phải được cập nhật. 4. Qúa trình định tuyến trong mạng TCP/IP TCP/IP là họ giao thức liên mạng nổi tiếng được Vint Cerf (Đại học Stanford) và Rebert Kahn (BBN) phát triển trong quá trình hình thành và phát triển mạng ARPANET, đó cũng là tiền thân của mạng Internet ngày nay cho phép kết nối các máy tính trên bình diện rộng lớn bao gồm nhiều quốc gia. Nhóm 28 – Cao học khóa 11 Trang 11 Tiểu luận lập trình mạng Định tuyến và giám sát đường đi gói tin Cơ sở hạ tầng cho quá trình định tuyến trong mạng TCP/IP bao gồm các thành phần sau: - - - Thiết bị định tuyến (Router/Gateway): Có chức năng quyết định đường đi của các gói tin trên mạng dựa vào thông tin của các bảng định tuyến được lưu trữ tại RAM. Một router sẽ phải học các đường (paths) hay các route từ việc cấu hình bằng tay bởi người quản trị hay có thể tự động cập nhật từ các router khác trong hệ thống dựa vào các giao thức định tuyến. Bảng định tuyến (Routing Table): là bảng chứa danh sách các đường định tuyến. Bảng định tuyến của mỗi giao thức định tuyến là khác nhau, nhưng có thể bao gồm nhữnh thông tin sau: địa chỉ đích của mạng, mặt nạ mạng của địa chỉ đích, địa chỉ IP của router chặng kế tiếp, cổng giao tiếp vật lý phải sử dụng để đi đến router kế tiếp, khoảng cách đến đích. Giao thức định tuyến (Routing Protocol): là ngôn ngữ để một router trao đổi với router khác để chia sẻ thông tin định tuyến về khả năng đến được cũng như trạng thái của mạng: RIP, IGRP, EIGRP, OSPF, IS-IS. Đường kết nối (Link Path): Các đường nối kết giữa các nút mạng với - nhau - Các thiết bị đầu cuối (host/terminal): Các thiết bị đầu cuối, nơi gửi và nhận dữ liệu Hub/Switch Router Link Path Host H 2.1: Các thành phần trong mạng TCP/IP Bảng định tuyến (tĩnh) lưu trữ trong Router A: Entry Network Address Netmask Gateway Interface 1 192.168.1.0 255.255.255.0 192.168.1.1 192.168.1.1 2 192.168.2.0 255.255.255.0 10.0.1.2 10.0.1.1 3 192.168.3.0 255.255.255.0 10.0.1.2 10.0.1.1 Để chọn lựa phương án triển khai giải quyết vấn đề chuyển gói tin trong mạng, người ta thường quan tâm hàng đầu đến độ tin cậy, ổn định và chi phí thực hiện của Nhóm 28 – Cao học khóa 11 Trang 12 Tiểu luận lập trình mạng Định tuyến và giám sát đường đi gói tin chúng. Một trong số các phương pháp định tuyến đã được nghiên cứu và triển khai áp dụng trong quá trình định tuyến trong mạng TCP/IP hiện nay: - Phương pháp cố định/tĩnh (Fixed Routing) - Phương pháp thích nghi/động (Adaptive Routing) Hầu hết các mạng viễn thông truyền thống được xây dựng theo mô hình mạng phân cấp, mô hình này cho phép sử dụng định tuyến tĩnh trên quy mô lớn. Trong khi định tuyến tĩnh vẫn còn tồn tại thì tính chất độc lập giữa người sử dụng và mạng vẫn ở mức cao; định tuyến tĩnh chủ yếu dựa trên mong muốn của người sử dụng nhiều hơn là tình trạng của mạng hiện thời. Mạng hiện đại ngày nay có xu hướng hội tụ các dịch vụ mạng, yêu cầu đặt ra từ phía người sử dụng là rất đa dạng và phức tạp. Các phương pháp định tuyến động được sử dụng nhằm nâng cao hiệu năng của mạng mới này, cho phép người sử dụng tham gia một phần vào quá trình quản lý mạng, tăng thêm tính chủ động, mềm dẻo, đáp ứng tốt hơn yêu cầu người sử dụng dịch vụ. 4.1. Phương pháp cố định (Fixed Routing) 4.1.1. Nguyên lý hoạt động Quá trình định tuyến theo phương pháp cố định (tĩnh) được thực hiện theo nguyên lý nội dung dữ liệu trong bảng định tuyến tại các nút mạng được người quản trị mạng cấu hình sẵn và không có sự thay đổi (cập nhật) trong suốt quá trình hoạt động của mạng. Quá trình truy vấn chọn đường được thực hiện như sau a. Trước tiên lần lượt thực hiện toán tử AND giữa địa chỉ đích đến trong gói với bitmask (Netmask) của route được chọn. Mỗi một route trong bảng được phân biệt với nhau bằng đích đến trong mạng của nó. b. Với mỗi route, kết quả thu được sau khi thực hiện phép toán AND sẽ được so sánh với trường địa chỉ đích của route, nếu tương xứng thì điều đó có nghĩa là route có thể được sử dụng để chuyển tiếp gói tin này đến địa chỉ đích của nó. Nếu có nhiều route cho kết quả hợp lệ thì sẽ sử dụng route tương xứng dài nhất (route có mặt nạ mạng có bit 1 cao nhất). Nếu đây không phải là một kết quả tương xứng duy nhất thì sẽ sử dụng sự tương xứng có mức hao phí thấp nhất (Metric). Cuối cùng, nếu có nhiều tương xứng có cùng một mức hao phí thấp nhất thì sẽ chọn một cách ngẫu nhiên một trong số những route như vậy để sử dụng. c. Sau cùng sẽ sử dụng thuật toán dưới đây để quyết định những gì cần thực hiện tiếp theo: + Nếu trường Gateway của route tương xứng với địa chỉ của một trong những giao diện mạng trên máy chủ (hoặc nếu Gateway là trống) thì sẽ gửi gói tin trực tiếp đến địa chỉ đích của nó bằng giao diện được chỉ định trong route. + Nếu trường Gateway của route không tương xứng với địa chỉ của bất kỳ giao diện mạng nào trên máy chủ thì Windows sẽ gửi gói tin đến địa chỉ trong trường Gateway của route. Nhóm 28 – Cao học khóa 11 Trang 13 Tiểu luận lập trình mạng Định tuyến và giám sát đường đi gói tin 4.1.2. Ví dụ minh họa Chúng ta hãy xem xét một mô hình định tuyến trong hệ thống mạng được cho bên dưới theo phương pháp cố định (tĩnh). H 2.2: Sơ đồ mạng minh họa trong định tuyến tĩnh Trong đó dữ liệu của Routing Table tại Gateway G1 được quản trị mạng cấu hình cố định như sau: Nhóm 28 – Cao học khóa 11 Trang 14 Tiểu luận lập trình mạng Định tuyến và giám sát đường đi gói tin Routing table tại gateway G1 Entry Network Destination Netmask Next-hop Interface (Gateway) Hop-count 1 128.192.6.0 255.255.255.0 128.192.6.250 128.192.6.250 0 2 128.192.150.0 255.255.255.0 128.192.150.250 128.192.150.250 0 3 128.192.232.0 255.255.255.0 128.192.232.250 128.192.232.250 0 4 131.144.4.10 255.255.255.255 128.192.232.2 128.192.232.250 1 5 168.15.0.0 255.255.0.0 128.192.232.2 128.192.232.250 2 6 0.0.0.0 0.0.0.0 128.192.232.2 128.192.232.250 1 Quá trình xử lý chọn đường xảy ra tại Gateway G1 đối với một số gói tin chuyển đến như sau: Ví dụ 1: Gói tin có địa chỉ đích là: 128.192.150.24 Sau khi thực hiện phép AND giữa địa chỉ đích và Netmask, ta có kết quả như sau Entry Netmask 128.192.150.24 (Router) AND Network Netmask Destination 1 255.255.255.0 128.192.150.0 128.192.6.0 2 255.255.255.0 128.192.150.0 128.192.150.0 3 255.255.255.0 128.192.150.0 128.192.232.0 4 255.255.255.255 128.192.150.24 131.144.4.10 5 255.255.0.0 128.192.0.0 168.15.0.0 6 0.0.0.0 0.0.0.0 0.0.0.0 Từ bảng định tuyến trên, ta có thể thấy được kết quả của phép tính AND cho hai kết quả tương xứng là 2 và 6 vì vậy sẽ sử dụng router 2 (router có sự tương xứng dài nhất) để chuyển gói tin đến địa chỉ đích của nó. Đây là những gì route này thể hiện trong bảng định tuyến. (Router) Network Destination Netmask Next-hop (Gateway) Interface 128.192.150.0 255.255.255.0 128.192.150.250 128.192.150.250 Nhóm 28 – Cao học khóa 11 Hop-count 0 Trang 15 Tiểu luận lập trình mạng Định tuyến và giám sát đường đi gói tin Ví dụ 2: Gói tin có địa chỉ đích là: 168.15.44.39 Sau khi thực hiện phép AND giữa địa chỉ đích và Netmask, ta có kết quả như sau (Router) Network Destination 168.15.44.39 Entry AND Netmask Netmask 1 255.255.255.0 168.15.44.0 128.192.6.0 2 255.255.255.0 168.15.44.0 128.192.150.0 3 255.255.255.0 168.15.44.0 128.192.232.0 4 255.255.255.255 168.15.44.39 131.144.4.10 5 255.255.0.0 168.15.0.0 168.15.0.0 6 0.0.0.0 0.0.0.0 0.0.0.0 Từ bảng định tuyến trên, ta có thể thấy được kết quả của phép tính AND cho hai kết quả tương xứng là 5 và 6 vì vậy sẽ sử dụng router 5 (router có sự tương xứng dài nhất) để chuyển gói tin đến địa chỉ đích của nó. Đây là những gì route này thể hiện trong bảng định tuyến. (Router) Network Destination 168.15.0.0 Next-hop Netmask 255.255.0.0 Interface Hop-count 128.192.232.250 2 (Gateway) 128.192.232.2 Ví dụ 3: Gói tin có địa chỉ đích là: 193.24.56.149 Sau khi thực hiện phép AND giữa địa chỉ đích và Netmask, ta có kết quả như sau 193.24.56.149 Entry Netmask AND Netmask (Router) Network Destination 1 255.255.255.0 193.24.56.0 128.192.6.0 2 255.255.255.0 193.24.56.0 128.192.150.0 3 255.255.255.0 193.24.56.0 128.192.232.0 4 255.255.255.255 193.24.56.0 131.144.4.10 5 255.255.0.0 193.24.0.0 168.15.0.0 6 0.0.0.0 0.0.0.0 0.0.0.0 Từ bảng định tuyến trên, ta có thể thấy được kết quả của phép tính AND cho một kết quả tương xứng là 6 vì vậy sẽ sử dụng router 6 để chuyển gói tin đến địa chỉ đích của nó. Đây là những gì route này thể hiện trong bảng định tuyến. Nhóm 28 – Cao học khóa 11 Trang 16 Tiểu luận lập trình mạng (Router) Netmask Network Destination 0.0.0.0 0.0.0.0 Định tuyến và giám sát đường đi gói tin Next-hop Interface Hop-count 128.192.232.250 1 (Gateway) 128.192.232.2 4.2. Phương pháp thích nghi/động (Adaptive Routing) 4.2.1. Nguyên lý hoạt động Phương pháp thích nghi là quá trình mà trong đó giao thức định tuyến dựa trên thông tin trạng thái hiện thời của mạng để tìm ra đường tốt nhất trong mạng và duy trì chúng. Thông tin trạng thái có thể đo hoặc dự đoán và tuyến đường có thể thay đổi khi topo mạng hoặc lưu lượng mạng thay đổi. Thông tin định tuyến cập nhật vào trong các bảng định tuyến của các nút (node) mạng trực tuyến, và đáp ứng tính thời gian thực nhằm tránh tắc nghẽn cũng như tối ưu hiệu năng mạng. Như vậy khác với phương pháp tĩnh, vấn đề dữ liệu trong các bảng định tuyến tại các nút mạng sẽ được tự động cập nhật dựa trên thông tin trạng thái thực tế của hệ thống mạng. Định tuyến thích nghi động xây dựng trên hai yếu tố cơ bản: Mô hình tính toán và thông tin trạng thái. Có hai kiểu mô hình tính toán sử dụng trong định tuyến động là mô hình tập trung và mô hình phân tán. Các thông tin trạng thái được trao đổi và cập nhật theo các giao thức định tuyến (RIP, IGRP, EIGRP, OSPF, IS-IS) Kỹ thuật định tuyến thích nghi động trong mạng TCP/IP được thực hiện qua các bước sau:  Quyết định chọn đường: Mỗi nút mạng (router) có một cơ sở dữ liệu mô tả tổng thể trạng thái của mạng (topo, độ trễ truyền dẫn,…). Các thông tin chứa trong cơ sở dữ liệu này được dùng để tính tóan các con đường tối ưu tới các nút khác (tức là tính cây chọn đường - Routing Tree) và đẩy các gói tin (datagram) theo các liên kết ra thích hợp. Giải thuật chọn đường tối ưu là giải thuật của Bellman-Ford hoặc Dijkstra đã được cải tiến. Tiêu chuẩn chọn đường được sử dụng trong giải thuật này được tính bởi độ trễ trung bình của các datagram trên các liên kết.  Đo độ trễ Độ trễ của một liên kết được đo như sau: Giả sử dt là độ trễ truyền một gói tin giữa hai nút hai đầu một liên kết dp là độ trễ truyền dẫn của liên kết (là hằng số đối với mỗi liên kết) dq là độ trễ xử lý và đợi trong nút gởi (nút nguồn) Khi đó, độ trễ tổng cộng d được tính như sau: d = dt+dp+dq Nhóm 28 – Cao học khóa 11 Trang 17 Tiểu luận lập trình mạng Định tuyến và giám sát đường đi gói tin Độ trễ trung bình trên liên kết được tính sau 10 giây một cho tất cả các datagram đi qua. Nếu độ trễ được tính này khác với độ trễ cũ (quá một ngưỡng cho trước nào đó) thì nó sẽ gởi đến tất cả các nút khác nhờ các đơn vị dữ liệu điều khiển (thông báo cập nhật). Ngoài ra, để đảm bảo độ tin cậy của việc cập nhật, một thông báo cập nhật sẽ luôn được gởi đi: - Sau một khỏang thời gian T, ngay cả nếu không có sự thay đổi nào; hoặc - Ngay sau khi có sự thay đổi trạng thái của một liên kết.  Cập nhật nội dung routing table Với giải thuật chọn đường mô tả ở trên, trong đó mỗi nút phải biết thông tin tổng thể của mạng, vấn đề truyền thông tin chọn đường (ở đây là độ trễ) trở nên rất quan trọng. Các thông báo cập nhật phải được nhận đúng để cho tất cả cơ sở dữ liệu ở các nút là như nhau (gắn bó dữ liệu). Phương pháp cập nhật nội dung routing table trong mạng TCP/IP như sau: Mỗi thông báo cập nhật của một nút chứa thông tin về độ trễ của tất cả các liên kết của nút đó. - Mỗi nút gởi thông báo cập nhật của mình tới tất cả các nút láng giềng (sau một khỏang thời gian T hoặc ngay lập tức sau khi có sự thay đổi đối với 1 liên kết). - Một router láng giềng khi nhận được một broadcast để cập nhật, router này sẽ so sánh với thông tin trong bảng định tuyến hiện giờ. Nếu trong các thông tin đó có một mạng mới, hay đường tới một mạng mới mà với độ trễ tốt hơn, chúng sẽ cập nhật vào bảng định tuyến. Sau đó router này sẽ tiếp tục broadcast thông tin trong bảng định tuyến của mình cho các router kế tiếp của nó.  Xử lý và chuyển gói tin Sau khi router nhận packet, the router sẽ gỡ bỏ header lớp 2 để tìm địa chỉ đích lớp 3. Sau khi đọc xong địa chỉ đích lớp 3 nó tìm kiếm trong routing table cho địa chỉ đích đó. Giả sử đỉa chỉ đích đó có trong routing table, router sẽ xác định địa chỉ của next-hop. Sau đó packet được đẩy ra buffer của interface tương ứng, router sẽ khám phá loại encapsulation lớp 2 nào được sử dụng giữa interface đi ra của gói tin và nexthop. Packet được đóng gói và chuyển xuống lớp 2 rồi đưa xuống môi trường truyền dẫn dưới dạng bit, tín hiệu điện, quang…Quá trình này sẽ tiếp tục cho đến khi packet được đưa đến đích . Như vậy một router phải xử lý và cập nhật thông tin bảng định tuyến của mình vừa đồng thời là một bộ chuyển tiếp (repeater) đối với các thông báo cập nhật đến từ các nút láng giềng của nó. Trong hình dưới đây là một ví dụ về Distance Vector Routing protocols (RIP/IGRP), chúng broadcast toàn bộ bảng định tuyến trên toàn bộ các cổng được cấu hình. Broadcast này có thể được coi như multicasting. Routers sử dụng các giao thức này sẽ không biết chính xác các router bên cạnh mà nó giao tiếp. Nhóm 28 – Cao học khóa 11 Trang 18 Tiểu luận lập trình mạng Định tuyến và giám sát đường đi gói tin H 2.3: Sơ đồ broadcast thông tin bảng định tuyến trong Distance Vector Routing Tuy nhiên, có vấn đề nảy sinh khi xảy ra sự phân rã mạng: một nút nào đó bị tách khỏi các nút khác và do vậy không thể nhận được các thông báo cập nhật đến từ các nút khác của mạng. Khi sự phân rã kết thúc, các nút vừa bị tách ra có thể nhận được các thông báo cập nhật “quá hạn”. Để cho phép một nút có thể loại bỏ được các thông báo “quá hạn” không còn giá trị đó, người ta định nghĩa một vùng “tuổi” trong mỗi thông báo cập nhật. Khi một thông báo được nhận, “tuổi” của nó được giảm theo số đơn vị thời gian đo được bởi một đồng hồ đặt ở mỗi nút. Một thông báo cập nhật được xem là “quá hạn” nếu vùng “tuổi” của nó có giá trị 0. Kỹ thuật truyền các thông báo cập nhật sử dụng trong TCP/IP còn được gọi là kỹ thuật “Intelligent Flooding” vì nó có thể nhận biết được thông báo trùng, vì nó chỉ gởi đi một thông báo mới và sau hết là vì nó gởi một thông báo cập nhật trên tất cả các liên kết, kể cả liên kết vào (tức là liên kết trên đó thông báo cập nhật vừa được tiếp nhận). Việc gởi thông báo cập nhật cả trên liên kết vào tạo ra một cơ chế báo nhận tự động cho các thông báo đó. Khi một nút nhận được từ một nút láng giềng một thông báo có cùng “tuổi” với thông báo mà nó vừa gởi đi cho nút láng giềng đó thì thông báo nhận được này sẽ xem như là một thông báo nhận. Hai thuật toán chọn đường thường được sử dụng phổ biến trong kỹ thuật định tuyến thích nghi động là: - Thuật toán định tuyến theo vector khoảng cách (Distance-Vector Routing) - Thuật toán định tuyến theo trạng thái liên kết (Link -State Routing).  Thuật toán định tuyến theo vector khoảng cách (Distance-Vector Routing) Thuật toán định tuyến theo vector khoảng cách (Distance-Vector Routing) nhằm tính toán con đường ngắn nhất giữa các cặp node (router) trong mạng dựa trên thuật toán Bellman-Ford. Các node mạng thực hiện quá trình trao đổi thông tin trên cơ sở của địa chỉ đích, node kế tiếp, và con đường ngắn nhất tới đích. Với thuật toán này, tại mỗi nút, các Router được giả định biết khoảng cách đến mỗi nút láng giềng của nó (có thể là độ trễ). Khi từng T msec mỗi Router gởi cho mỗi láng giềng một danh sách các độ trễ ước tính của nó đến từng nút láng giềng và nó cũng nhận được một danh sách tương tự từ các nút láng giềng. Xét một trong các bảng chọn đường đến từ nút láng giềng X, với X i là ước tính thời gian X cần đến Router i. Nếu Router biết độ trễ đến X là m msec thì nó cũng biết đến router i qua X là (X i + m) msec. Thực hiện phép tính này với mỗi nút láng giềng, một router có thể tìm ra độ trễ tốt nhất (nhỏ nhất) và nó dùng độ trễ này để cập nhật lại giá trị đường tương ứng trong bảng chọn đường mới. Nhóm 28 – Cao học khóa 11 Trang 19 Tiểu luận lập trình mạng Định tuyến và giám sát đường đi gói tin Chi tiết của thuật toán Bellman – Ford được mô tả như sau: Giả thuyết: - Cho một đồ thị G(V,E) trong đó V là tập đỉnh và E là tập cạnh có trọng - Đỉnh nguồn S: S  V số Yêu cầu: Xác định đường đi ngắn nhất từ đỉnh nguồn S đến tất cả các đỉnh còn lại. Ký hiệu: D(S)I : Giá trị đường đi (độ trễ) ngắn nhất từ node nguồn S đến node I - ở bước hiện tại - P(S)I : Nút láng giềng mà S đi qua với đường đi ngắn nhất đến node I. - dIJ : trọng số trên cạnh nối trực tiếp từ node I đến node J. dIJ = 0 nếu I trùng J hoặc dIJ = EIJ nếu I khác J Giải thuật: - Bước 1: Khởi động D(S)I = dSI, I  V\{S}; P(S)I = I nếu dSI  ∞ hoặc P(S)I = Null nếu dSI = ∞ - Bước 2: Cập nhật đường đi ngắn nhất D(S)I = min{ dSJ +D(J)I }, J  V\{S} P(S)I = J Bước 3: Lặp lại bước 2 cho đến khi không có đường đi mới nào ngắn hơn đường đi đã được tìm thấy, nghĩa là D(S)I không có sự thay đổi qua 2 lần chạy liên tiếp với I  V\{S} thì dừng. - Bước 4: Xác định D(S)I sẽ là giá trị đường đi ngắn nhất từ node S đến nút I thông qua nút láng giềng là giá trị của P(S)I. -  Thuật toán định tuyến theo trạng thái liên kết (Link -State Routing) Link-State Routing dựa trên thuật toán Dijkstra, bình thường nó còn được gọi là thuật toán Shortest Path First (SPF). Các router chạy một giao thức Link-State liên quan trực tiếp tới trạng thái (state) của một cổng trên router khác trong hệ thống mạng. Một Link-State router xây dựng toàn bộ dữ liệu về tất cả các trạng thái từ tất cả các router trong một vùng. Một nghĩa khác, một Link-State router lấy đủ các thông tin để chúng có thể vẽ lên một bản đồ của hệ thống mạng. Mỗi router sau khi chạy thuật toán SPF trong bản đồ do chúng xây dựng, hay dữ liệu về link-state, để nhận ra một đường đi tốt nhất nhằm thiết lập trong routing table. Router sẽ quảng bá thông tin Link-State này tới tất cả các router trên mạng. Toàn bộ quá trình quảng bá này được gọi là Link-state Advertiesements (LSAs). Không như Distance Vector Routers, Link-State Routers có thể thiết lập những mỗi quan hệ đặc biệt giữa các router khác để đảm bảo rằng thông tin LSA được truyền Nhóm 28 – Cao học khóa 11 Trang 20