Đề tài Các thuật toán và phương thức định tuyến trong mạng

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN ĐIỆN TỬ VIỄN THÔNG ******************** BÀI TẬP LỚN MÔN HỌC: TỔ CHỨC VÀ QUY HOẠCH MẠNG VIỄN THÔNG Đề tài: “Các Thuật Toán Và Phương Thức Định Tuyến Trong Mạng ” Giảng viên hướng dẫn: Nguyễn Văn Thắng Nhóm sinh viên thực hiện: Họ và tên SHSV Lớp š&› HÀ NỘI 4/2012 Mục Lục Mở đầu Một trong những hoạt động của mạng nói chung là việc truyền dữ liệu từ nguồn tới đích. Định tuyến là một chức năng không thể tách rời của mạng khi truyền dữ liệuh từ nguồn tới đích và có ý nghĩa đặc biệt quan trọng trong việc thiết kế và tối ưu mạng. Cấu trúc mạng, giải pháp công nghệ và phương pháp định tuyến là 3 vấn đề liên quan mật thiết với nhau và quyết định chất lượng hoạt động của mạng. Chính vì vậy, bài toán định tuyến cần được quan tâm nghiên cứu để nhằm tối ưu hóa hiệu suất sử dụng tài nguyên mạng. Trên thế giới đã có nhiều nghiên cứu về các phương pháp định tuyến, với mục đích chủ yếu là tìm ra những phương pháp định tuyến thích hợp để áp dụng vào thực tế mạng lưới. Trong thời gian gần đây, xu hướng định tuyến theo “giá” trên mạng đã trở thành một chủ đề nghiên cứu quan trọng. Thông thường, lợi ích mang lại trên mạng được tối đa bằng việc tối ưu hóa các hàm mục tiêu. Tùy thuộc vào cấu trúc và các đường truyền trên mạng mà các hàm mục tiêu và ràng buộc đi theo sẽ khác nhau. Nội dung Giới thiệu về định tuyến: Định tuyến là quá trình tìm đường đi để truyền tải thông tin trong liên mạng từ nguồn đến đích. Nó là một chức năng được thực hiện ở tầng mạng. Chức năng này cho phép router đánh giá các đường đi sẵn có tới đích. Để đánh giá đường đi, định tuyến sử dụng các thông tin về Topology của mạng. Các thông tin này có thể do người quản trị thiết lập. Quá trình định tuyến cần thỏa mãn các yêu cầu cho trước bao gồm: đường đi ngắn nhất hoặc có băng thông rộng nhất. Đường đi thường phải tối ưu theo một trong hai tiêu chí.các gói tin có thể được gửi đi theo đường này. Nhưng cũng có thể chúng được gửi đi đồng thời trên nhiều đường . Việc định tuyến được sử dụng cho nhiều loại mạng: mạng viễn thông, liên mạng, internet, mạng giao thông. Hình 1: Tìm đường đi tiếp theo Định tuyến có thể được chia ra làm 3 phương pháp định tuyến: định tuyến tĩnh, định tuyến ngẫu nhiên và định tuyến động. Trong môi trường mạng thường xuyên có sự thay đổi ngẫu nhiên nên định tuyến tĩnh chỉ có ý nghĩa ở các gateway và các mạng nhỏ. Trong định tuyến động, có hai phương thức định tuyến: tìm đường theo đường đi ngắn nhất và tìm đường đi tối ưu. Vấn đề tìm đường đi ngắn nhất được đặt ra: ta có thể tìm đường đi ngắn nhất từ một nút đến tất cả các nút khác hoặc tìm đường đi ngắn nhất từ một nút đến một nút cụ thể. Cách giải quyết này được sử dụng trong giao thức OSPF(Open Shortest Path First) với việc sử dụng các thuật toán Dijikstra, Bellman-Ford. Ngoài ra ta có thể để các nút mạng tự động tìm ra đường đi tối ưu. Việc tim ra tuyến đi được thực hiện một cách phân tán tại các nút chứ không do một nút trung tâm tính toán. Các nút chủ động trao đổi thông tin liên quan đến cấu hình mạng với nhau. Từ các thông tin thu thập được mỗi nút tự tìm ra đường đi tối ưu đến các nút khác rồi lập ra bảng định tuyến đưa ra quyết định định tuyến. Bảng định tuyến thường xuyên được cập nhật mỗi khi có thay đổi cấu hình mạng. Thuật toán được sử dụng là Prime và Kruskal nhằm tạo ra cây bắc cầu tối thiểu. Các khái niệm trong lý thuyết graph: Phần này giới thiệu các thuật ngữ và các khái niệm cơ bản nhằm mô tả các mạng, graph, và các thuộc tính của nó. Lý thuyết graph là một môn học xuất hiện từ lâu, nhưng lý thuyết này có một số thuật ngữ được chấp nhận khác nhau dùng cho các khái niệm cơ bản. Vì thế có thể sử dụng một số thuật ngữ khác nhau để lập mô hình graph cho mạng. Các thuật ngữ được trình bày dưới đây này là các thuật ngữ đã được công nhận và được sử dụng thường xuyên chương này. Một graph G, được định nghiã bởi tập hợp các đỉnh V và tập hợp các cạnh E. Các đỉnh thường được gọi là các nút và chúng biểu diễn vị trí (ví dụ một điểm chứa lưu lượng hoặc một khu vực chứa thiết bị truyền thông). Các cạnh được gọi là các liên kết và chúng biểu diễn phương tiện truyền thông. Graph có thể được biểu diễn như sau: G=(V, E) Hình 2 là một ví dụ của một graph. Hình 2: Một graph đơn giản Mặc dù theo lý thuyết, V có thể là tập hợp rỗng hoặc không xác định, nhưng thông thường V là tập hợp xác định khác rỗng, nghĩa là có thể biểu diễn V={vi | i=1,2,......N} Trong đó N là số lượng nút. Tương tự E được biểu diễn: E={ei | i=1,2,......M} Một liên kết, ej, tương ứng một kết nối giữa một cặp nút. Có thể biểu diễn một liên kết ej giữa nút i và k bởi ej=(vi,vk) hoặc bởi ej=(i,k) Một liên kết gọi là đi tới một nút nếu nút đó là một trong hai điểm cuối của liên kết. Nút i và k gọi là kề nhau nếu tồn tại một liên kết (i, k) giữa chúng. Những nút như vậy được xem là các nút láng giềng. Bậc của nút là số lượng liên kết đi tới nút hay là số lượng nút láng giềng. Hai khái niệm trên là tương đương nhau trong các graph thông thường. Tuy nhiên với các graph có nhiều hơn một liên kết giữa cùng một cặp nút, thì hai khái niệm trên là không tương đương. Trong trường hợp đó, bậc của một nút được định nghĩa là số lượng liên kết đi tới nút đó. Một liên kết có thể có hai hướng. Khi đó thứ tự của các nút là không có ý nghiă. Ngược lại thứ tự các nút có ý nghĩa. Trong trường hợp thứ tự các nút có ý nghĩa, một liên kết có thể được xem như là một cung và được định nghĩa aj=[vi,vk] hoặc đơn giản hơn aj=[i,k] k được gọi là cận kề hướng ra đối với i nếu một cung [i,k] tồn tại và bậc hướng ra của i là số lượng các cung như vậy. Khái niệm cận kề hướng vào và bậc cận kề hướng vào cũng được định nghĩa tương tự. Một graph gọi là một mạng nếu các liên kết và các nút có mặt trong liên kết có các thuộc tính (chẳng hạn như độ dài, dung lượng, loại...). Các mạng được sử dụng để mô hình các vấn đề cần quan tâm trong truyền thông, các thuộc tính riêng biệt của nút và liên kết thì liên quan đến các vấn đề cụ thể trong truyền thông. Sự khác nhau giữa các liên kết và các cung là rất quan trọng cả về việc lập mô hình cho mạng lẫn quá trình hoạt động bên trong của các thuật toán, vì vậy sự khác nhau cần phải luôn được phân biệt rõ ràng. Về mặt hình học các liên kết là các đường thẳng kết nối các cặp nút còn các cung là các đường thẳng có mũi tên ở một đầu, biểu diễn chiều của cung. Một graph có các liên kết gọi là graph vô hướng, tuy nhiên một graph có các cung gọi là graph hữu hướng. Một graph hữu hướng có thể có cả các liên kết vô hướng. Thông thường , các graph được giả sử là vô hướng, hoặc sự phân biệt đó là không có ý nghĩa. Có thể có khả năng xảy ra hiện tượng xuất hiện nhiều hơn một liên kết giữa cùng một cặp nút (điều này tương ứng với việc có nhiều kênh thông tin giữa hai chuyển mạch). Những liên kết như vậy được gọi là các liên kết song song. Một graph có liên kết song song gọi là một multigraph. Cũng có khả năng xuất hiện các liên kết giữa một nút nào đó và chính nút đó. Những liên kết đó được gọi là các self loop. Chúng ít khi xuất hiện và thường xuất hiện do việc xem hai nút như là một nút trong quá trình lập mô hình graph cho một mạng hoặc phát sinh trong quá trình thực hiện một thuật toán có việc hợp nhất các nút. Hình 4.2 minh hoạ một graph có các liên kết song song và các self loop. Một graph không có các liên kết song song hoặc các self loop gọi là một graph đơn giản. Việc biểu diễn và vận dụng các graph đơn giản là tương đối dễ dàng, vì vậy giả thiết rằng các graph được xem xét là các graph đơn giản. Nếu có sự khác biệt với giả thiết này, chúng sẽ được chỉ ra. Phân loại định tuyến : Hình 3: Phân loại định tuyến Định tuyến tĩnh: Đối với định tuyến tĩnh các thông tin về đường đi phải do người quản trị mạng cập nhật cho các router. Khi cấu trúc mạng có bất kỳ thay đổi nào thì chính người quản trị mạng phải xóa hoặc thêm các thông tin về đường đi cho các router. Những loại này gọi là đường đi cố định. Đối với hệ thống mạng nhỏ, ít có thay đổi thì công việc này đỡ mất công hơn. Chính vì định tuyến đòi hỏi người quản trị mạng phải cấu hình mọi thông tin về đường đi cho các router nên nó không có được tính linh hoạt như định tuyến động. Trong những hệ thống mạng lớn, định tuyến tĩnh thường được sử dụng kết hợp với giao thức định tuyến động cho một số mục đích đặc biệt. Hoạt động của định tuyến tĩnh có thể chia làm 3 bước như sau: Đầu tiên, người quản trị mạng cấu hình các đường cố định cho các router Router cài đặt các đường đi này vào bảng định tuyến Gói dữ liệu được định tuyến theo các đường đi cố định này Sau đây là demo cấu hình của mạng định tuyến tĩnh Hình 4: Demo cấu hình mạng định tuyến Định tuyến ngẫu nhiên (random routing): Định tuyến ngẫu nhiên lan tràn gói (flooding): Một dạng mạnh hơn của định tuyến riêng biệt đó là lan tràn gói. Trong phương thức này, mỗi gói đi đến router sẽ được gửi đi trên tất cả các đường ra trừ đường mà nó đi đến. Phương thức lan tràn gói này hiển nhiên là tạo ra rất nhiều gói sao chép (duplicate). Trên thực tế, số gói này là không xác định trừ khi thực hiện một số biện pháp để hạn chế quá trình này. Một trong những biện pháp đó là sử dụng bộ đếm bước nhảy trong phần tiêu đề của mỗi gói. Giá trị này sẽ bị giảm đi một tại mỗi bước nhảy. Gói sẽ bị loại bỏ khi bộ đếm đạt giá trị không. Về mặt lý tưởng, bộ đếm bước nhảy sẽ có giá trị ban đầu tương ứng với độ dài từ nguồn đến đích. Nếu như người gửi không biết độ dài của đường đi, nó có thể đặt giá trị ban đầu của bộ đếm cho trường hợp xấu nhất. Khi đó giá trị ban đầu đó sẽ được đặt bằng đường kính của mạng con. Một kỹ thuật khác để ngăn sự lan tràn gói là thêm số thứ tự vào tiêu đề các gói. Mỗi router sẽ cần có một danh sach theo nút nguồn để chỉ ra những số thứ tự từ nguồn đó đã được xem xét. Để tránh danh sách phát triển không giới hạn, mỗi danh sách sẽ tăng lên bởi số đếm k để chỉ ra rằng tất cả các số thứ tự đến k đã được xem. Khi một gói đi tới, rất dễ dàng có thể kiểm tra được gói là bản sao hay không. Nếu đúng gói là bản sao thì gói này sẽ bị loại bỏ. Tức là khi nhận được mỗi gói tin,nút mạng sẽ gủi đi tất cả các nút kề cận,trừ nút đã gửi gói cho nó.Lan tràn gói có ưu điểm là lan tràn gói luôn luôn chọn đường ngắn nhất. Có được ưu điểm này là do về phương diện lý thuyết nó chọn tất cả các đường có thể do đó nó sẽ chọn được đường ngắn nhất. Tuy nhiên nhược điểm của nó là số lượng gói gửi trong mạng quá nhiều. Sử dụng lan tràn gói trong hầu hết các ứng dụng là không thực tế. Tuy vậy lan tràn gói có thể sử dụng trong những ứng dụng sau. Trong ứng dụng quân sự, mạng sử dụng phương thức lan tràn gói để giữ cho mạng luôn luôn hoạt động tốt khi đối mặt với quân địch. Hình 5: Định tuyến lan tràn gói Trong những ứng dụng cơ sở dữ liệu phân bố, đôi khi cần thiết phải cập nhật tất cả cơ sở dữ liệu. Trong trường hợp đó sử dụng lan tràn gói là cần thiết. Ví dụ sự dụng lan tràn gói để gửi cập nhật bản định tuyến bởi vì cập nhật không dựa trên độ chính xác của bảng định tuyến. 40 Phương pháp lan tràn gói có thể được dùng như là đơn vị để so sánh phương thức định tuyến khác. Lan tràn gói luôn luôn chọn đường ngắn nhất. Điều đó dẫn đến không có giải thuật nào có thể tìm được độ trễ ngắn hơn. Một biến đổi của phương pháp lan tràn gói là lan tràn gói có chọn lọc. Trong giải thuật này, router chỉ gửi gói đi ra trên các đường mà đi theo hướng đích. Điều đó có nghĩa là không gửi gói đến những đường mà rõ ràng nằm trên hướng sai Định tuyến ngẫu nhiên (random walk): Trong phương pháp định tuyến này, router sẽ chuyển gói đi đến trên một đường đầu ra được chọn một cách ngẫu nhiên. Mục tiêu của phương pháp này là các gói lang thang trong mạng cuối cùng cũng đến đích. Với phương pháp này giúp cho quá trình cân bằng tải giữa các đường. Cũng giống như phương pháp định tuyến lan tràn gói, phương pháp này luôn đảm bảo là gói cuối cùng sẽ đến đích. So với phương pháp trước thì sự nhân rộng gói trong mạng sẽ ít hơn. Nhược điểm của phương pháp này là đường từ nguồn đến đích có thể dài hơn đường ngắn nhất. Do đó trễ đường truyền sẽ dài hơn sẽ trễ ngắn nhất thực sự tồn tại trong mạng. Gói tin được gửi đến mỗi đầu ra với một xác xuất nào đó So với flooding,số lượng gói truyền đi nhỏ hơn Đường đi ngắn nhất có thể không nằm trong số đường được chọn Hình 6: Định tuyến ramdom walk Định tuyến ngẫu nhiên (hot potato): Định tuyến riêng biệt là loại định tuyến mà router quyết định định tuyến đi chỉ dựa vào thông tin bản thân nó lượm lặt được. Đây là một thuật toán tương thích riêng biệt (isolated adaptive algorithm). Khi một gói đến một nút, router sẽ cố gắng chuyển gói đó đi càng nhanh càng tốt bằng cách cho nó vào hàng chờ đầu ra ngắn nhất. Nói cách khác, khi có gói đi đến router sẽ tính toán số gói được nằm chờ để truyền tren mỗi đường đầu ra. Sau đó nó sẽ gán gói mới vào cuối hàng chờ ngắn nhất mà không quan tâm đến đường đó sẽ đi đâu. Hình 7 biễu diễn các hàng chờ đầu ra bên trong một router tại một thời điểm nào đó. Có ba hàng chờ đầu ra tương ứng với 03 đường ra. Các gói đang xếp hàng trên mỗi đường để chờ được truyền đi. Trong ví dụ ở đây, hàng chờ đến F là hàng chờ ngắn nhất với chỉ có một gói nằm trên hàng chờ này. Giải thuật khoai tây nóng do đó sẽ đặt gói mới đến vào hàng chờ này. Hình 7: Định tuyến ngẫu nhiên Có thể biến đổi ý tưởng này một chút bằng cách kết hợp định tuyến tĩnh với giải thuật khoai tây nóng. Khi gói đi đến, router sẽ tính đến cả những trọng số tĩnh của đường dây và độ dài hàng chờ. Một khả năng là sử dụng lựa chọn tĩnh tốt nhất trừ khi độ dài hàng chờ lớn hơn một ngưỡng nào đó. Một khả năng khác là sử dụng độ dài hàng chờ ngắn nhất trừ trọng số tĩnh của nó là quá thấp. Còn một cách khác là sắp xếp các đường theo trọng số tĩnh của nó và sau đó lại sắp xếp theo độ dài hàng chờ của nó. Sau đó sẽ chọn đường có tổng vị trí sắp xếp là nhỏ nhất. Dù giải thuật nào được chọn đi chăng nữa cũng có đặc tính là khi ít tải thì đường có trọng số cao nhất sẽ được chọn, nhưng sẽ làm cho hàng chờ cho đường này tăng lên. Sau đó một số lưu lượng sẽ được chuyển sang đường ít tải hơn. Định tuyến động (dynamic routing):  Là quá trình mà trong đó giao thức định tuyến tìm ra đường tốt nhất trong mạng và duy trì chúng. Có rất nhiều cách để xây dựng lên bảng định tuyến một cách động. Nhưng tất cả đều thực hiện theo quy tắc sau: nó sẽ khám tất cả các tuyến đường đến đích có thể và thực hiện một số quy tắc được định trước để xác định ra đường tốt nhất đến đích. Ưu điểm của dynamic routing là đơn giản trong việc cấu hình và tự động tìm ra những tuyến đường thay thế nếu như mạng thay đổi. Nhược điểm của dynamic routing là yêu cầu xử lý của CPU của router cao hơn là static route. Tiêu tốn một phần băng thông trên mạng để xây dựng lên bảng định tuyến. Định tuyến động (minimum spanning tree): Có thể sử dụng quá trình trình duyệt để tìm một cây bắc cầu nếu có một cây bắc cầu tồn tại. Cây tìm được thường là cây vô hướng. Việc tìm cây "tốt nhất" thường rất quan trọng . Chính vì vậy, chúng ta có thể gắn một "độ dài" cho mỗi cạnh trong graph và đặt ra yêu cầu tìm một cây có độ dài tối thiểu. Thực tế, "độ dài" có thể là khoảng cách, giá, hoặc là một đại lượng đánh giá độ trễ hoặc độ tin cậy. Một cây có tổng giá là tối thiểu được gọi là cây bắc cầu tối thiểu. Nói chung, nếu graph là một graph không liên thông, chúng ta có thể tìm được một rừng bắc cầu tối thiểu. Một rừng bắc cầu tối thiểu là một tập hợp các cạnh nối đến graph một cách tối đa có tổng độ dài là tối thiểu. Bài toán này có thể được xem như là việc lựa chọn một graph con của graph gốc chứa tất cả các nút của graph gốc và các cạnh được lựa chọn. Đầu tiên, tạo một graph có n nút, n thành phần và không có cạnh nào cả. Mỗi lần, chúng ta chọn một cạnh để thêm vào graph này hai thành phần liên thông trước đó chưa được kết nối được liên kết lại với nhau tạo ra một thành phần liên thông mới (chứ không chọn các cạnh thêm vào một thành phần liên thông trước đó và tạo ra một vòng). Vì vậy, tại bất kỳ giai đoạn nào của thuật toán, quan hệ: n=c+e . luôn được duy trì, ở đây n là số lượng nút trong graph, e là số cạnh được lựa chọn tính cho tới thời điểm xét và c là số lượng thành phần trong graph tính cho tới thời điểm xét. Ở cuối thuật toán, e bằng n trừ đi số thành phần trong graph gốc; nếu graph gốc là liên thông, chúng ta sẽ tìm được một cây có (n-1) cạnh. Quá trình duyệt cây sẽ tìm ra một rừng bắc cầu. Tuy nhiên, chúng ta thường không tìm được cây bắc cầu có tổng độ dài tối thiểu. Để tìm ra cây bắc cầu tối thiểu người ta sử dụng 2 thuật toán: prime và kruskal. Định tuyến động (shortest path tree): Bài toán tìm các đường đi ngắn nhất là một bài toán khá quan trọng trong quá trình thiết kế và phân tích mạng. Hầu hết các bài toán định tuyến có thể giải quyết như giải quyết bài toán tìm đường đi ngắn nhất khi một "độ dài " thích hợp được gắn vào mỗi cạnh (hoặc cung) trong mạng. Trong khi các thuật toán thiết kế thì cố gắng tìm kiếm cách tạo ra các mạng thoả mãn tiêu chuẩn độ dài đường đi. Bài toán đơn giản nhất của loại toán này là tìm đường đi ngắn nhất giữa hai nút cho trước. Loại bài toán này có thể là bài toán tìm đường đi ngắn nhất từ một nút tới tất cả các nút còn lại, tương đương bài toán tìm đường đi ngắn nhất từ tất cả các điểm đến một điểm. Đôi khi đòi hỏi phải tìm đường đi ngắn nhất giữa tất cả các cặp nút. Các đường đi đôi khi có những giới hạn nhất định (chẳng hạn như giới hạn số lượng các cạnh trong đường đi). Tiếp theo, chúng ta xét các graph hữu hướng và giả sử rằng đã biết độ dài của một cung giữa mỗi cặp nút i và j là lij. Các độ dài này không cần phải đối xứng. Khi một cung không tồn tại thì độ dài lij được giả sử là rất lớn (chẳng hạn lớn gấp n lần độ dài cung lớn nhất trong mạng). Chú ý rằng có thể áp dụng quá trình này cho các mạng vô hướng bằng cách thay mỗi cạnh bằng hai cung có cùng độ dài. Ban đầu giả sử rằng lij là dương hoàn toàn; sau đó giả thiết này có thể được thay đổi. Loại định tuyến này được dùng thông dụng với các thuật toán được dùng: dijkstra, bellman ford. Các thuật toán dùng để định tuyến: Thuật toán Prim: Thuật toán này có những ưu điểm riêng biệt là khi mạng dày đặc,trong việc xem xét một bài toán tìm kiếm các cây bắc cầu tối thiểu. Hơn nữa các thuật toán phức tạp hơn được xây dựng dựa vào các thuật toán cây bắc cầu tối thiểu,và một số thuật toán này hoạt động tốt hơn với các cấu trúc dữ liệu được sử dụng cho thuật toán sau đây,thuật toán này được phát biểu bởi Prim. Các thuật toán này phù hợp với các quad trình thực hiện song song bởi vì các quá trình đó được thực hiện bằng các toán tử vector. Thuật toán được miêu tả như sau: B1: Chọn một đỉnh s bất kỳ của G cho vào cây T. Khi đó cây T là một cây chỉ có một đỉnh và chưa có cạnh nào. B2: Nếu T đã gồm tất cả các đỉnh của G thì T là cây bao trùm cần tìm. Kết thúc. B3: Nếu G còn có các đỉnh không thuộc T ,vì G liên thông nên có các cạnh nối một đỉnh trong T với một đỉnh ngoài T, chọn một cạnh có trọng số nhỏ nhất trong số đó cho vào T. B4: Quay lại B2. Ví dụ: Hình minh họa U Cạnh (u,v) V \ U Mô tả {} {A,B,C,D,E,F,G} Đây là đồ thị có trọng số ban đầu. Các số là các trọng số của các cạnh. {D} (D,A) = 5 V(D,B) = 9(D,E) = 15(D,F) = 6 {A,B,C,E,F,G} Chọn một cách tùy ý đỉnh D là đỉnh bắt đầu. Các đỉnh A, B, Evà F đều được nối trực tiếp tớiD bằng cạnh của đồ thị. A là đỉnh gần D nhất nên ta chọn A là đỉnh thứ hai của cây và thêm cạnh ADvào cây. {A,D} (D,B) = 9(D,E) = 15(D,F) = 6 V(A,B) = 7 {B,C,E,F,G} Đỉnh được chọn tiếp theo là đỉnh gần D hoặc Anhất. B có khoảng cách tớiD bằng 9 và tớiA bằng 7, E có khoảng cách tới cây hiện tại bằng 15, và F có khoảng cách bằng 6. F là đỉnh gần cây hiện tại nhất nên chọn đỉnh F và cạnhDF. {A,D,F} (D,B) = 9(D,E) = 15(A,B) = 7 V(F,E) = 8(F,G) = 11 {B,C,E,G} Thuật toán tiếp tục tương tự như bước trước. Chọn đỉnhB có khoảng cách tới A bằng 7. {A,B,D,F} (B,C) = 8(B,E) = 7 V(D,B) = 9 chu trình(D,E) = 15(F,E) = 8(F,G) = 11 {C,E,G} Ở bước này ta chọn giữa C, E, và G. C có khoảng cách tớiB bằng 8, E có khoảng cách tớiB bằng 7, và Gcó khoảng cách tới F bằng 11. Elà đỉnh gần nhất, nên chọn đỉnh Evà cạnh BE. {A,B,D,E,F} (B,C) = 8(D,B) = 9 chu trình(D,E) = 15 chu trình(E,C) = 5 V(E,G) = 9(F,E) = 8 chu trình(F,G) = 11 {C,G} Ở bước này ta chọn giữa C vàG. C có khoảng cách tới E bằng 5, và G có khoảng cách tớiE bằng 9. ChọnC và cạnh EC. {A,B,C,D,E,F} (B,C) = 8 chu trình(D,B) = 9 chu trình(D,E) = 15 chu trình(E,G) = 9 V(F,E) = 8 chu trình(F,G) = 11 {G} Đỉnh G là đỉnh còn lại duy nhất. Nó có khoảng cách tới F bằng 11, và khoảng cách tới E bằng 9. E ở gần hơn nên chọn đỉnh Gvà cạnh EG. {A,B,C,D,E,F,G} (B,C) = 8 chu trình(D,B) = 9 chu trình(D,E) = 15 chu trình(F,E) = 8 chu trình(F,G) = 11 chu trình {} Hiện giờ tất cả các đỉnh đã nằm trong cây và cây bao trùm nhỏ nhất được tô màu xanh lá cây. Tổng trọng số của cây là 39. Thuật toán Kruskal: B1: khởi tạo T lúc đầu là một đồ thị rỗng. B2: nếu T đã gồm đúng n-1 cạnh của G thì t là cây bao trùm cần tìm. Kết thúc. B3: nếu T còn chưa đủ n-1 cạnh,thì vì G liên thông, nên G có không ít hơn n-1 cạnh, do đó còn các cạnh của G chưa thuộc T. trong các cạnh của G chưa thuộc t có các cạnh không tạo ra chu trình với các cạnh đã có trong T, chọn cạnh v có trọng số nhỏ nhất trong các cạnh ấy bổ sung vào T. Loại bỏ những cạnh tạo thành chu trình. B4: quay lại B2. VÍ DỤ: Ảnh minh họa Mô tả AD và CE là các cạnh nhỏ nhất với độ dài 5, và ta chọn AD một cách tùy ý (tô màu xanh). CE là cạnh nhỏ nhất không tạo thành chu trình với độ dài 5, nên nó là cạnh thứ hai được chọn. Cạnh thứ ba DF với độ dài 6 cũng được chọn tương tự như vậy. Các cạnh tiếp theo theo thứ tự trọng số tăng dần là AB và BE, với độ dài 7. Chọn AB một cách tùy ý. Cạnh BD không thể được chọn trong tương lai (tô màu đỏ) vì đã có đường nối B và D nên nếu chọn nó sẽ tạo thành chu trình ABD. Tiếp tục chọn cạnh nhỏ nhất tiếp theo là BE với độ dài 7. Thêm một số cạnh được tô màu đỏ: BC vì nó sẽ tạo chu trình BCE, DE vì nó sẽ tạo chu trình DEBA, và FE vì nó sẽ tạo chu trình FEBAD. Cuối cùng, thuật toán chọn cạnh EG độ dài 9, và tìm ra cây bao trùm nhỏ nhất. Thuật toán Dijkstra: Cho Graph liên thông G={V,E}, cần tìm khoảng cách ngắn nhất và đường đi từ nút s đến tất cả các nút khác. B1: thiết lập i=0, tập chứa các nút có giá cố định S={uo= s}, gán d(v) bằng: ∞ với v≠uo 0 với v= uo Nếu | V|= 1 thì kết thúc. B2: với mỗi v € V/S, thay thế :d(v)= min{d(v),d(ui)+ d(vui)}. Nếu d(v) thay đổi giá trị, đặt nhãn (d(v), ui) cho v. B3: trong số các v vừa được cập nhật giá, tìm Ui+1 có giá nhỏ nhất. gán S=S(ui+1) B4: thay thế bởi i+1. Nếu i =|V|-1 kết thúc. Nếu không quay về B2. Thuật toán Bellman Ford: Cho graph liên thông G={V,E},cần tìm khoảng cách ngắn nhất và đường đi từ nút s đến tất cả các nút khác. B1: thiết lập hàm xác định nút tiền bối cảu s là π(s)= s và các giá d(v) bằng: =∞ với v≠uo =0 với v =uo Tạo dàng đợi FIFO Q của các nút quét. Đưa s vào Q. B2: lấy ra đỉnh đầu tiên trong hàng đợi h, kiểm tra giá của các nút lân cận U,nếu d(u )> d(h)+ d(hu) thì đưa u vào hàng đợi và gán: d(u)= d(h)+ d(hu) π(u)= h B3: lặp lại B2 cho đến khi Q={Ø} Một số giao thức định tuyến động hiện nay: Để quản trị mạng dễ dàng hơn, người ta đã cố gắng nghiên cứu định tuyến động theo các hướng khác nhau như: tìm đường đi ngắn nhất và tìm đường đi tối ưu nhất. Điển hình cho hai hướng nghiên cứu đó là hai giao thức định tuyến: RIP (tìm đường đi ngắn nhất) và OSPF (tìm đường đi tối ưu nhất), ngoài ra người ta còn phát triển thêm giao thức EIGRP là giao thức định tuyến lai giữa hai giao thức trên để lợi dụng ưu điểm của mỗi loại giao thức. Hình 8: Phân loại các giao thức định tuyến Giao thức định tuyến RIP (Routing Information Protocol): Giao thức định tuyến RIP là giao thức định tuyến “distance vector” – định tuyến theo khoảng cách từ nút cho tới mạng đích. Hiện nay giao thức này đã được nghiên cứu và phát triển đến version 3, trong đó vesion 2 được sử dụng nhiều nhất. Chúng đều sử dụng “hop count” là giá của đường đi tới mạng đích, trong đó mỗi “hop count” là một nút mạng có chức năng hoạt động ở lớp 3 trong mô hình OSI. Và giá của đường đi có giá trị từ 0 đến 15. Cứ mỗi 30 giây thì các nút mạng gửi thông tin bảng định tuyến cho nhau để cập nhật dữ liệu về đường đi tới các mạng đích và duy trì kết nối. Giao thức này sử dụng thuật toán Bellman-Ford so sánh giá của các liên kết để xây dựng nên bảng định tuyến và định tuyến gói tin. Ví dụ trên nút mạng R1 ta sử dụng chương trình theo dõi bản tin cập nhật dữ liệu bảng định tuyến, sau mỗi thời gian nhất định nút mạng gửi yêu cầu nút mạng khác gửi thông tin định tuyến về để xây dựng bảng định tuyến của riêng mình. Trong bảng định tuyến có chứa thông tin về mạng đích, cổng đi tới mạng đích và giá của đường tới mạng đích đó là bao nhiêu. Hình 9: Quá trình gưi thông tin định tuyến ở RIP Nhược điểm của giao thức định tuyến này là dễ dẫn tới gói tin trong mạng bị lặp vòng (loop) do thời gian các nút mạng gửi thông tin định tuyến cho nhau là định kì, và trong thời gian khá lâu trong khi môi trường mạng luôn có sự thay đổi ngẫu nhiên. Đồng thời giao thức này không phân biệt loại gói tin được truyền đi trong mạng nên với những gói tin là thời gian thực vẫn bị xử lí giống những gói tin dữ liệu thường, tức là giao thức không hỗ trợ QoS (Quality of Service). Ngoài ra, vì giá được tính theo số “hop count” nên có thể có trường hợp giá của liên kết thì nhỏ trong khi băng thông cũng nhỏ thì sẽ gây nghẽn mạng, mà liên kết có giá lớn hơn nhưng băng thông lớn thì lại không có dữ liệu được truyền. Do đó giao thức này chỉ được sử dụng ở các mạng nhỏ, và dung lượng mạng không quá lớn để tránh tình trạng nghẽn mạng gây mất dữ liệu do bị lặp vòng quá nhiều. OSPF (Open Shortest Path First): Giao thức OSPF được phát triển năm 1987 bởi IETF (Internet Engineering Task Force). Đây là giao thức “link-state” – hoạt động dựa trên thông tin về trạng thái các liên kết trong mạng. Mỗi nút mạng nhận và gửi các gói tin LSU (Link State Update) tới các nút mạng khác về trạng thái liên kết của nó tới các mạng khác như thế nào, từ đó xây dựng nên cây SPF (Shortest Path First) bằng thuật toán Dijkstra. Ở đây, giá được sử dụng bằng cách tính toàn từ băng thông của các liên kết, băng thông càng lớn thì giá càng nhỏ, cho thấy sự tối ưu về cách tính giá liên kết so với giao thức RIP. Khi mỗi nút mạng biết được bất kì sự thay đổi nảo về trạng thái liên kết tới mạng khác thì nó mới gửi dữ liệu định tuyến cập nhật tới nút mạng khác. Do đó, bình thường không có sự thay đổi nào về mạng thì các nút mạng chỉ gửi những gói có kích thước không đáng kể để duy trì liên kết, còn khi có thay đổi thì chỉ gửi thông tin về sự thay đổi đó, dẫn tới giảm lượng băng thông cho toàn mạng. Trong mạng đa truy cập OSPF (các nút mạng sử dụng giao thức OSPF trao đổi thông tin với nhau cùng nối vào thiết bị ở lớp 2 mô hình OSI – như Hình 10) có cơ chế bầu chọn nút mạng chủ (BDR), nút mạng này chịu trách nhiệm cập nhật thông tin định tuyến cho các nút khác dựa vào thông tin định tuyến từ các nút thay đổi tới nó. Do đó hạn chế được tình trạng tốn băng thông do các nút mạng trao đổi thông tin định tuyến với nhau hoặc gây nghẽn mạng tại thiết bị trung tâm. Hình 10: Ưu điểm của BDR Ưu điểm của giao thức này là mạng hội tụ nhanh do chỉ cập nhật khi mạng có sự thay đổi và chỉ cập nhật những liên kết bị thay đổi. Đồng thời, do giá được tính toán theo băng thông của các liên kết nên tăng được tốc độ lưu thông thông tin trên toàn mạng. EIGRP (Enhanced Interior Gateway Routing Protocol): Đây là giao thức định tuyến do Cisco IOS Software Release xây dựng từ năm 1992 và chỉ hoạt động trên các thiết bị mạng do Cisco sản xuất. Giao thức này sử dụng thuật toán Bellman-Ford hoặc Ford-Fulkerson, là hai thuật toán định tuyến theo khoảng cách. Nhưng quá trình hoạt động cập nhật bảng định tuyến thì EIGRP lại hoạt động giống như OSPF, tức cập nhật định tuyến theo trạng thái liên kết. Nhờ vậy, giống OSPF, giao thức EIGRP tăng dung lượng của mạng hơn hẳn so với giao thức định tuyến RIP. Đồng thời, giá của mỗi liên kết được tính toán dựa vào bốn thông số: băng thông, trễ, độ tin cậy và tải. Dựa vào bốn thông số này, mỗi thông tin định tuyến trong đường đi được tính toán tối ưu, đảm bảo cho các gói tin trong mạng luôn được truyền đi với độ tin cậy cao nhất. Ngoài ra, giao thức OSPF còn giúp người quản trị mạng thực hiện quản trị mạng tối ưu hơn bằng cách phân vùng tự trị cho các vùng lân cận nhau. Mỗi vùng tự trị là một AS: Hình 11: Ưu điểm của phân vùng tự trị (AS) Mỗi AS chạy một định tuyến EIGRP chung và chỉ định tuyến trong AS đó, muốn định tuyến dữ liệu sang mạng khác thì các nút mạng phải định tuyến tĩnh tới nút mạng biên (Gateway). Ở đây, ta lại thấy định tuyến tĩnh cũng có chức năng đặc biệt trong mạng. Hai giao thức OSPF và EIGRP có hỗ trợ xác thực bản tin update nên có tính bảo mật rất cao, cùng với update thông tin định tuyến mỗi khi có sự thay đổi của trạng thái liên kết nên có ưu thế vượt trội so với giao thức định tuyến RIP. Nhưng bù lại mỗi nút mạng cần yêu cầu tốc độ xử lí cao, do đó hai giao thức này chủ yếu được sử dụng trong mạng lõi. Với mạng nhỏ với số lượng người dùng ít người ta sử dụng định tuyến RIP để chi phí thiết bị rẻ hơn, và dễ cấu hình sử dụng hơn. Kết luận Định tuyến lưu lượng trong mạng đã trải qua những giai đoạn phát triển quan trọng. Với sự phát triển nhanh chóng của công nghệ viễn thông và máy tính, các phương pháp định tuyến mạng ngày càng trở nên linh hoạt gắn liền với hiệu quả của hoạt động mạng lưới, kế hoạch định tuyến trở thành một thành phần không thể thiếu được trong công tác thiết kế, xây dựng và vận hành, quản lý mạng. Qua quá trình tìm hiểu về định tuyến từ sách báo và internet, bài tập lớn của chúng em đưa ra các vấn đề: Định tuyến. Phương pháp định tuyến (các loại định tuyến). Thuật toán định tuyến và ví dụ. Giao thức định tuyến ứng dụng các thuật toán. Bài tập lớn của chúng em còn nhiều thiếu sót, rất mong được sự chỉ bảo của thầy giáo. Em xin chân thành cảm ơn thầy! Tài liệu tham khảo [1] Rick Graziani - Allan Johnson, Routing Protocols And Concepts. Cisco Press, 2008. [2] Donald Gross, Carl M. Harris, Fundamentals of Queueing Theory, Wiley-Interscience,1998 [3] Joseph L. Hammond, Peter J.P.O' Reilly, Performance Analysis of Local Computer Networks, Addison-Wesley, 1988 [4] Slide giảng dạy môn Cơ sở mạng thông tin, TS. Nguyễn Văn Tiến, Viện Điện tử viễn thông, Đại học Bách Khoa Hà Nội . [5] Slide giảng dạy môn Mạng máy tính, Giảng viên Nguyễn Hữu Thanh, Viện Điện tử viễn thông, Đại học Bách Khoa Hà Nội.