Bài giảng Mạng thông tin

TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT HƯNG YÊN KHOA ĐIỆN-ĐIỆN TỬ BÀI GIẢNG MẠNG THÔNG TIN Hưng Yên 2015 (Tài liệu lưu hành nội bộ) KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -3- Chƣơng 1. CÁC KHÁI NIỆM CƠ BẢN VỀ MẠNG THÔNG TIN 1.1. TỔNG QUAN VỀ MẠNG THÔNG TIN Nội dung chính của chƣơng này đƣợc trình bày theo các mục chính và đƣợc sắp xếp theo trình, cụ thể: Thông tin và truyền thông đây là một trong những vấn vấn đề đang đƣợc xã hội quan tâm trong nền kinh tế mới, nền kinh tế thông tin, nền kinh tế trí thức, nền kinh tế học hỏi và nền kinh tế số; trang bị về cái nhìn tổng quát về mạng số liệu; tổ chức về mạng truyền số liệu hiện đại, các kỹ thuật đƣợc dùng trong truyền số liệu và những vấn đề căn bản trong chuẩn hóa và mô hình tham chiếu của mạng 1.1.1 Thông tin và truyền thông Thông tin liên lạc đóng vai trò hết sức quang trọng trong cuộc sống, hầu hết chúng ta luôn gắn liền với một vài dạng thông tin nào đó. Các dạng trao đổi tin có thể nhƣ: đàm thoại ngƣời với ngƣời, đọc sách, gửi và nhận thƣ, nói chuyện qua điện thoại, xem phim hay truyền hình, xem triển lãm tranh , tham dự diễn đàn . . . Có hàng nghìn ví dụ khác nhau về thông tin liên lạc, trong đó gia công chế biến để truyền đi trong thông tin số liệu là một phần đặc biệt trong lĩnh vực thông tin. Hình 1.1. Một hệ thống thông tin cơ bản ở đây: AP- Applicayion process- Quá trình ứng dụng Từ các ví dụ trên chúng ta nhận thấy rằng mỗi hệ thống truyền tin đều có các đặc trƣng riêng nhƣng có một số đặc tính chung cho tất cả các hệ thống. Đặc trƣng chung có tính nguyên lý là tất cả các hệ thống truyền tin đều nhằm mục đích chuyển tải thông tin từ điểm này đến điểm khác. Trong các hệ thống truyền số liệu, thƣờng gọi thông tin là dữ liệu hay thông điệp. Thông điệp có nhiều dạng khác nhau, để truyền thông điệp từ một điểm này đến điểm khác cần phải có sự tham gia của 3 thành phần của hệ thống: nguồn Hệ thống phục truyền tin AP Hệ thống phục vụ phục truyền tin AP Máy tính A Máy tính B Thông tin user đến user Thông tin máy tính đến máy tính Thông tin máy tính đến mạng Mạng truyền số liệu KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -4- tin là nơi phát sinh và chuyển thông điệp lên môi trƣờng truyền; môi trƣờng truyền là phƣơng tiện mang thông điệp tới đích thu. Các phần tử này là yêu cầu tối thiểu trong bất cứ quá trình truyền tin nào. Nếu một trong các thành phần này không tồn tại, truyền tin không thể xảy ra. Một hệ thống truyền tin thông thƣờng đƣợc miêu tả trên hình 1.1. Các thành phần cơ bản có thể xuất hiện dƣới dạng khác nhau tuỳ thuộc vào hệ thống. Khi xây dựng các thành phần của một hệ thống truyền tin, cần phải xác định một số các yếu tố liên quan đến phẩm chất hoạt động của nó. Để truyền tin hiệu quả các chủ để phải hiểu đƣợc thông điệp. Nơi thu nhận thông điệp phải có khả năng dịch thông điệp một cách chính xác. Điều này là hiển nhiên bởi vì trong giao tiếp hàng ngày nếu chúng ta dùng một từ mà ngƣời ta không thể hiểu thì hiệu quả thông tin không đạt yêu cầu. Tƣơng tự, nếu máy tính mong muốn thông tin đến với tốc độ chỉ định và ở một dạng mã nào đó nhƣng thông tin lại đến với tốc độ khác và với dạng mã khác thì rõ ràng không thể đạt đƣợc hiệu quả truyền. Các đặc trƣng toàn cục của một hệ thống truyền đƣợc xác định và bị giới hạn bởi các thuộc tính riêng của nguồn tin, của môi trƣờng truyền và đích thu. Nhìn chung, dạng thông tin cần truyền quyết định kiểu nguồn tin, môi trƣờng và đích thu. Trong một hệ thống truyền, hiện tƣợng nhiễu có thề xảy ra trong tiến trình truyền và thông điệp có thể bị ngắt quãng. Bất kỳ sự xâm nhập không mong muốn nào vào tín hiệu đều bị gọi là nhiễu. Có nhiều nguồn nhiễu và nhiều dạng nhiễu khác nhau. Hiểu biết đƣợc các nguyên tắc căn bản về truyền tin sẽ giúp chúng ta dễ dàng tiếp cận một lĩnh vực đặc biệt hấp dẫn đó là thông tin số liệu.Thông tin số liệu liên quan đến một tổ hợp nguồn tin, môi trƣờng và máy thu trong các kiểu mạng truyền số liệu khác nhau. 1.1.2 Các dạng thông tin và xử lý thông tin Tất cả những gì mà con ngƣời muốn trao đổi với nhau đƣợc hiểu là thông tin những thông tin nguyên thuỷ này đƣợc gia công chế biến để truyền đi trong không gian đƣợc hiểu là tín hiệu. Tuỳ theo việc sử dụng đƣờng truyền, tín hiệu có thể tạm chia tín hiệu thành hai dạng: tín hiệu điện-từ và tín hiệu không phải điện từ. Việc gia công tín hiệu cho phù hợp với mục đích và phù hợp với đƣờng truyền vật lý đƣợc gọi là xử lý tín hiệu. Ngày nay với sự phát triển của công nghệ tin học đã tạo ra một công nghệ mới về truyền số liệu. Máy tính với những tính năng vô cùng to lớn đã trở thành hạt nhân trong việc xử lý thông tin, điều khiển các quá trình truy nhập số liệu, máy tính và các hệ thống thông tin tạo thành một hệ thống truyền số liệu. Có 2 nguồn thông tin đó là thông tin tƣơng tự và thông tin số. Trong đó nguồn thông tin tƣơng tự liên tục theo sự thay đổi của giá trị vật lý thể hiện thông tin với đặc tính chất KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -5- lƣợng nhƣ tiếng nói, tín hiệu hình ảnh , còn nguồn thông tin số là tín hiệu gián đoạn thể hiện thông tin bởi nhóm các giá trị gián đoạn xác định đặc tính chất lƣợng bằng quan hệ với thời gian nhƣ tín hiệu số liệu. Thông tin số có nhiều ƣu điểm hơn so với thông tin tƣơng tự nhƣ : thông tin số có nhiều khả năng chống nhiễu tốt hơn vì nó có các bộ lặp để tái tạo lại tín hiệu, cung cấp chất lƣợng truyền dẫn tốt hơn với các khoảng cách, nó kết hợp đƣợc mọi nguồn dịch vụ hiện đang có, nó tạo ra đƣợc một tổ hợp truyền dẫn số và tổng đài số. Những phần tử bán dẫn dùng trong truyền dẫn số là những mạch tổ hợp nó đƣợc sản xuất hàng loạt, và mạng liên lạc trở thành mạng thông minh vì dễ chuyển đổi tốc độ cho các loại dịch vụ khác nhau thay đổi thủ tục, xử lý tín hiệu số (DSP) chuyển đổi phƣơng tiện truyền dẫn ... Hệ thống thông tin số cho phép thông tin điều khiển đƣợc cài đặt vào và tách dòng thông tin thực hiện một cách độc lập với với bản chất của phƣơng tiện truyền tin ( cáp đồng trục, cáp sợi quang, vi ba, vệ tinh..),. Vì vậy thiết bị báo hiệu có thể thiết kế riêng biệt với hệ thống truyền dẫn. Chức năng điều khiển có thể thay đổi mà không phụ thuộc vào hệ thống truyền dẫn, ngƣợc lại hệ thống có thể nâng cấp không ảnh hƣởng tới các chức năng điều khiển ở cả 2 đầu của đƣờng truyền 1.2 Khái quát mạng truyền số liệu Hình 1.2. Mô hình mạng truyền số liệu hiện đại Ngày nay với sự phát triển của kỹ thuật và công nghệ đã tạo ra một bƣớc tiến dài trong lĩnh vực truyền số liệu. Sự kết hợp giữa phần cứng, các giao thức truyền thông các thuật toán đã tạo ra các hệ thống truyền số liệu hiện đại, những ký thuật cơ sở vẫn đƣợc dùng nhƣng chúng đƣợc xử lý tinh vi hơn. Về cơ bản một hệ thống truyền số liệu hiện đại mô tả nhƣ hình 1.2 Giao tiếp DTE-DCE DTE DCE Hệ thống truyền (nhận) tin Giao tiếp DTE-DCE DCE DTE Hệ thống nhận (truyền) tin Kênh truyền tin KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -6- a. DTE (Data Terminal Equipment – Thiết bị đầu cuối dữ liệu) Đây là thiết bị lƣu trữ và xử lý thông tin. Trong hệ thống truyền số liệu hiện đại thi DTE thƣờng là máy tính hoặc máy Fax hoặc là trạm cuối (terminal). Nhƣ vậy tất cả các ứng dụng của ngƣời sử dụng (chƣơng trình, dữ liệu) đều nằm trong DTE Chức năng của DTE thƣờng lƣu trữ các phần mềm ứng dụng , đóng gói dữ liệu rồi gửi ra DCE hoặc nhận gói dữ liệu từ DCE theo một giao thức (protocol) xác định DTE trao đổi với DCE thông qua một chuẩn giao tiếp nào đó. Nhƣ vậy mạng truyền số liệu chính là để nối các DTE lại cho phép chúng ta phân chia tài nguyên, trao đổi dữ liệu và lƣu trữ thông tin dùng chung b. DCE (Data Circuit terminal Equipment- Thiết bị cuối kênh dữ liệu) Đây là thuật ngữ dùng để chỉ các thiết bị dùng để nối các DTE với các đƣờng (mạng) truyền thông nó có thể là một Modem, Multiplexer, Card mạng...hoặc một thiết bị số nào đó nhƣ một máy tính nào đó trong trƣờng hợp máy tính đó là một nút mạng và DTE đƣợc nối với mạng qua nút mạng đó. DCE có thể đƣợc cài đặt bên trong DTE hoặc đứng riêng nhƣ một thiết bị độc lập. Trong thiết bị DCE thƣờng có các phần mềm đƣợc ghi vào bộ nhớ ROM phần mềm và phần cứng kết hợp với nhau để thực hiện nhiệm vụ của nó vẫn là chuyển đổi tín hiệu biểu diễn dữ liệu của ngƣời dùng thành dạng chấp nhận đƣợc bởi đƣờng truyền. Giữa 2 thiết bị DTE việc trao đổi dữ liệu phải tuân thủ theo chuẩn, dữ liệu phải gửi theo một Format xác định. Thí dụ nhƣ chuẩn trao đổi dữ liệu tầng 2 của mô hình 7 lớp là HDLC (High level Data Link Control) Trong máy Fax thì giao tiếp giữa DTE và DCE đã thiết kế và đƣợc tích hợp vào trong một thiết bị, phần mềm điều khiển đƣợc cài đặt trong ROM. c. Kênh truyền tin Kênh truyền tin là môi trƣờng mà trên đó 2 thiết bị DTE trao đổi dữ liệu với nhau trong phiên làm việc DTE C D E F DTE Hình 1.3. Kênh thông tin ở đây: C, D-Modem; E, F- Transducer Trong môi trƣờng thực này 2 hệ thống đƣợc nối với nhau bằng một đoạn cáp đồng trục và một đoạn cáp sợi quang, modem C để chuyển đổi tín hiệu số sang tín hiệu tƣơng tự để truyền trong cáp đồng trục modem D lại chuyển tín hiệu đó thành tín hiệu số và qua Tranducer E để chuyển đổi từ tín hiệu điện sang tín hiệu quang để truyền trên cáp sợi Cáp đồng trục Cáp sợi quang KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -7- quang cuối cùng Tranducer F lại chuyển tín hiệu quang thành tín hiệu điện để tới DTE 1.4. Mạng truyền số liệu Mạng truyền số liệu bao gồm hai hay nhiều hệ thống truyền (nhận) tin nhƣ hình 1.2 đƣợc ghép nối với nhau theo nhiều hình thức nhƣ phân cấp hoặc phân chia thành các trung tâm xử lý trao đổi tin với các chức năng riêng ... Mạng truyền số liệu là một hệ thống nhằm kết nối các máy tính lại với nhau, sự thông tin giữa chúng đƣợc thực hiện bởi các giao thức đã đƣợc chuẩn hoá, có nghĩa các phần mềm trong các máy tính khác nhau có thể cùng nhau giải quyết một công việc hoặc trao đổi thông tin với nhau. Các ứng dụng tin học ngày càng rộng rãi do đó đã đẩy các hƣớng ứng dụng mạng xử lý số liệu, mạng đấu nối có thể có cấu trúc tuyến tính cấu trúc vòng cấu trúc hình sao... Cấu trúc mạng phải có khả năng tiếp nhận các đặc thù khác nhau của các đơn vị tức là mạng phải có tính đa năng, tính tƣơng thích. Mạng số liệu đƣợc thiết kế nhằm mục đích có thể nối nhiều thiết bị đầu cuối với nhau. Để truyền số liệu ta có thể dùng mạng điện thoại hoặc dùng đƣờng truyền riêng có tốc độ cao. Dịch vụ truyền số lỉệu trên kênh thoại là một trong các dịch vụ đầu tiên của việc truyền số liệu. Trên mạng này có thể có nhiều máy tính cùng chủng loại hoặc khác loại đƣợc ghép nối lại với nhau, khi đó cần giải quyết những vấn đề phân chia tài nguyên. Để các máy tính ở các đầu cuối có thể làm việc đƣợc với nhau cần phải có cùng một protocol nhất định. Dạng thức của phƣơng tiện truyền số liệu đƣợc qui định bởi bản chất tự nhiên của ứng dụng, bởi số lƣợng máy tính liên quan và khoảng cách vật lý giữa chúng. Các dạng truyền số liệu trên có các dạng sau: a. Nếu chỉ có hai máy tính và cả hai đều đặt ở một văn phòng, thì phƣơng tiện truyền số liệu có thể chỉ gồm một liên kết điểm nối đơn giản, hình 1.4. Tuy nhiên, nếu chúng liên kết ở những vị trí khác nhau trong một thành phố hay một quốc gia thì phải cần đến các phƣơng tiện truyền tải công cộng. Mạng điên thoại công cộng đƣợc dùng nhiều nhất, trong trƣờng hợp này sẽ cần đến bộ thích nghi gọi là Modem. Sắp xếp truyền theo dạng này đƣợc trình bày trên hình1.4 KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -8- Hình 1.4. Truyền số liệu nối qua mạng điện thoại công cộng dùng modem b. Khi cần nhiều máy tính trong một ứng dụng, một mạng chuyển mạch sẽ đƣợc dùng cho phép tất cả các máy tính có thể liên lạc với nhau vào bất cứ thời điểm nào. Nếu tất cả máy tính đều nằm trong một toà nhà , có thể xây dựng một mạng riêng .Một mạng nhƣ vậy đƣợc xem nhƣ mạng cục bộ LAN (Local Area Network) .Nhiều chuẩn mạng LAN và các thiết bị liên kết đã đƣợc tạo ra cho các ứng dụng thực tế . Hai hệ thống mạng Lan cơ bản đƣợc trình bày trên hình 1.5 Hình 1.5. Các hệ thống LAN cơ bản (liên kết LAN qua backbone trong một văn phòng) Khi máy tính đƣợc đặt ở nhiều nơi cách xa nhau cần liên lạc với nhau, phải dùng đến các phƣơng tiện công cộng .Việc liên kết máy tính này tạo nên một mạng rộng lớn, đƣợc gọi là mạng diện rộng WAN (Wide Area Network). Kiểu mạng WAN đƣợc dùng phụ thuộc vào tƣờng ứng dụng tự nhiên. Ví dụ nếu tất cả các máy tính đều thuộc về một công ty và có yêu cầu truyền một số lƣợng dữ liệu quan trọng giữa các điểm , thì giải pháp đơn giản nhất cho vắn đề là thuê các Hệ thống phục truyền tin AP Hệ thống phục vụ phục truyền tin AP PSTN Modem Modem Hệ thống phục truyền tin AP Hệ thống phục vụ phục truyền tin AP KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -9- đƣờng truyền từ nhà cung cấp phƣơng tiện truyền dẫn và xây dựng hệ thống chuyển mạch riêng tại một đIểm để tạo thành mạng tƣ nhân. Các giải pháp thuê kênh chỉ hiệu quả đối với các công ty lớn vì có tải hữu ích để cân đối với giá thuê kênh. Trong hầu hết các trƣờng hợp khác đều cần đến các mạng truyền dẫn công cộng. Bên cạnh việc cung cấp dịch vụ điện thoại công cộng, ngày nay hầu hết các nhà cung cấp dịch vụ truyền dẫn đều cung cấp một dịch vụ chuyển mạch số liệu mang tính công cộng. Thật ra các mạng này tƣơng tự nhƣ mạng PSTN là đƣợc liên kết quốc tế, chỉ khác ở chỗ đƣợc thiết kế chuyên cho truyền số liệu. Nhƣ vậy các ứng dụng liên quan đến máy tính đƣợc phục vụ bởi mạng số liệu chuyển mạch công cộng PSDN. Ngoài ra còn có thể chuyển đổi các mạng PSTN có sẵn sao cho có thể truyền đƣợc số liệu mà không cần dùng modem. Các mạng này hoạt động trong chế độ số (digital) hoàn toàn đƣợc gọi là mạng số liên kết đa dịch vụ ISDN 1.4.1. Phân loại mạng truyền số liệu Mạng truyền số liệu đa dạng về chủng loại cũng nhƣ về số lƣợng , có nhiều cách phân chia mạng số liệu, bao gồm: a. Phân loại theo địa lý: Mạng nội bộ, Mạng diện rộng và Mạng toàn cầu b. Phân loại theo tính chất sử dụng mạng: Mạng truyền số liệu kí sinh và Mạng truyền số liệu chuyên dụng. c. Phân loại theo topo mạng: Mạng tuyến tính, Mạng hình sao và Mạng vòng d. Phân loại theo kỹ thuật: Mạng chuyển mạch kênh, Mạng chuyển mạch gói và Mạng chuyển mạch thông báo 1.4.2. Kỹ thuật chuyển mạch giữa các node trong mạng Để thực hiện việc liên lạc giữ các thuê bao ngƣời ta tạo ra mạng liên lạc với các NODE. Các thuê bao đƣợc nối đến các node . các thuê bao đƣợc nối vào mạng thông qua các Node. Số lƣợng các node phụ thuộc vào độ lớn của mạng, nhƣ vậy mỗi thuê bao chị cần một cổng I/O. Mỗi mạng bao gồm các Node , các node đƣợc nối với nhau , số liệu sẽ truyền từ ngƣời gửi đến ngƣời nhận theo con đƣờng thông qua mạng, các Node đƣợc nối với nhau theo hƣớng truyền, số liệu đƣợc định đƣờng từ Node này sang node này sang node khác. a. Kỹ thuật chuyển mạch kênh Liên lạc thông qua chuyển mạch kênh đặc trƣng bởi việc cung cấp các đƣờng nối cố định giữa 2 thuê bao. Sự liên lạc qua mạng chuyển mạch kênh bao gồm 3 giai đoạn : xác lập, truyền số liệu và giải phóng mạch KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -10- * Xác lập mạch Trƣớc khi có thể truyền số liệu , đƣờng truyền cần đƣợc thiết lập, Từ thuê bao truy nhập vào một node, node này cần phải tìm các nhánh đi qua một số node khác để đến đƣợc thuê bao bị gọi việc tìm kiếm này dựa vào các thông tin về tìm đƣờng và các thông số khác, cuối cùng khi 2 node thuộc thuê bao gọi và bị gọi đƣợc nối với nhau nó cần kiểm tra xem node thuộc thuê bao bị gọi có bận không. Nhƣ vậy là con đƣờng nối từ thuê bao gọi đến thuê bao bị gọi đã đƣợc thiết lập * Truyền số liệu Thông tin bắt đầu truyền từ điểm A đến điểm E có thể trong dạng số hoặc tƣơng tự qua điểm nối mạch bên trong mỗi node, sự nối mạch cho phép truyền 2 chiều toàn phần và dữ liệu có thể truyền 2 chiều. * Giải phóng mạch Sau khi hoàn thành sự truyền, có tín hiệu báo của thuê bao gọi (A) hoặc bị gọi (E) báo cho các node trung gian giải phóng sự nối mạch, đƣờng nối từ A đến E không còn nữa. Đƣờng nối đƣợc thiết lập trƣớc khi truyền dữ liệu nhƣ vậy dung lƣợng các kênh cần phải dự trữ cho mỗi cặp thuê bao và ở mỗi node cũng phải có lƣợng chuyển mạch tƣơng ứng bên trong để bảo đảm bảo đƣợc sự yêu cầu nối mạch. Trong bộ chuyển mạch số lƣợng kênh nối phải bảo đảm bảo suốt cả quá trình yêu cầu nối cho dù có hay không có dữ liệu truyền qua. Tuy nhiên khi đƣờng nối giữa 2 thuê bao đƣợc nối thì dữ liệu đƣợc truyền trên một đƣờng cố định. b. Kỹ thuật chuyển mạch thông báo Chuyển mạch kênh có 2 nhƣợc điểm: - 2 thuê bao cần phải hoạt động trong cùng thời gian truyền - Những nguồn cung cấp cũng phải ổn định và cung cấp qua mạng giữa 2 thuê bao Hiện nay những bức điện báo, thƣ điện tử, Files của máy tính đƣợc gọi là những thông báo và nó đƣợc truyền qua mạng nhƣ sự trao đổi những dữ liệu số đƣợc trao đổi 2 chiều giữa các thuê bao. Một trong những loại mạch để phục vụ sự trao đổi thông tin đó đƣợc gọi là chuyển mạch thông báo. Với chuyển mạch thông báo không tồn tại sự thiết lập và cung cấp lộ trình cố định giữa 2 thuê bao, mỗi thuê bao muốn truyền một thông báo, nó sẽ gán địa chỉ của ngƣời nhận vào thông báo. Thông báo sẽ đƣợc chuyển qua mạng từ node này qua node khác.Tại mỗi node thông báo đƣợc nhận tạm giữ và chuyển sang node khác. Các node thông thƣờng là những KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -11- máy tính nó giữ thông báo ở bộ đệm. Thời gian trễ ở mỗi bộ đệm bao gồm cả thời gian nhận thông báo vào node và thời gian xếp hàng chờ để đến lƣợt mình đƣợc chuyển đến node sau. Hệ thống chuyển mạch thông báo là hệ thống luôn giữ và chuyển tiếp. c. Chuyển mạch gói Chuyển mạch gói gần giống chuyển mạch thông báo. Chỗ khác nhau cơ bản là độ dài của một khối dữ liệu đƣa vào mạng đƣợc chế thành các gói và đƣợc gửi đi tại từng thời điểm, mỗi gói bao gồm dữ liệu cùng với địa chỉ và các thông số cần thiết, các gói không phải là file. Trong mạng chuyển mạch gói có 2 cách truyền gói đƣợc dùng: Datagram và Virtual Circuit 1. DATAGRAM: các gói là độc lập giống nhƣ trong chuyển mạch thông báo, các thông báo độc lập nhau. Cách truyền nhƣ vậy, mỗi gói độc lập đƣờng đi có thể không giống nhau gọi là DATAGRAM (DG) 2. MẠCH ẢO (Virtual Circuit): Trong mạch ảo sự nối logic mạch đƣợc thiết lập trƣớc khi truyền mỗi gói, mỗi gói bây giờ gồm cả nhận dạng VC và dữ liệu. Mỗi Node với con đƣờng đã định biết đƣợc cần phải truyền gói trực tiếp đến đâu không cần phải tìm đƣờng nữa. Một trong 2 trạm sẽ chấm dứt kết nối bằng cách truyền gói CLEAR REQUEST Cùng một thời gian một trạm có thể có nhiều VC đến một trạm khác và có thể có nhiều VC đến nhiều trạm khác. Nhƣ vậy tính chất cơ bản của VC là đƣờng nối logic giữa 2 trạm đƣợc thiết lập trƣớc khi truyền dữ liệu , điều đó không có nghĩa là có một con đƣờng cụ thể nhƣ trong chuyển mạch kênh. Gói đƣợc giữ ở một node và sắp hàng để đƣợc đƣa ra trên đƣờng nối. Chỗ khác với DATAGRAM là trong VC NODE không cần tìm đƣờng cho mỗi gói mà nó chỉ làm một lần cho một lần nối. Chú ý: Nếu một Node bị hƣ tất cả các VC qua Node đều bỏ, còn với DG nếu node đó bị hƣ thì gói tìm con đƣờng khác. Những điều chính yếu của mạng chuyển mạch gói là: Routing: Chức năng đầu tiên của PS là nhận những gói từ trạm nguồn và cung cấp nó đến ngƣời nhận, để hoàn thành việc đó, một hoặc nhiều con đƣờng thông qua mạng đƣợc chọn, thông thƣờng khả năng cho phép nhiều hơn 1. Điều đó có nghĩa là con đƣờng đƣợc chọn cần phải đảm bảo một số yêu cầu cần thiết trong chức năng đƣờng truyền nhƣ chính xác , đơn giản, ổn định hợp lý tối ƣu. Sự chọn đƣờng dựa vào tiêu chuẩn đơn giản là chọn đƣờng ngắn nhất ( một đƣờng với KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -12- node ít nhất ) thông qua mạng. Thực tế là ngƣời ta thƣờng dùng các con đƣờng có thời gian đi là nhỏ nhất, Nhƣng không phải khi nào con đƣờng đi có thời gian nhỏ nhất cũng là con đƣờng ngắn nhất. Giá trị nhỏ nhất bao gồm cho từng đƣờng và đƣờng thông qua mạng bao gồm tích luỹ giá trị bé nhất của các đƣờng thành phần, Những điểm cần quyết định khi lựa chọn gồm: - Sự quyết định về thời gian - Sự quyết định về vị trí - Routing phân tán - Routinh tập trung Một trong những cách tìm đƣờng đơn giản là tìm đƣờng cố định. Trong trƣờng hợp đó, một con đƣờng đƣợc xác định cho một cặp nguồn. Một thƣ mục tìm đƣờng tại trung tâm đƣợc tạo nên. thƣ mục cho ta Node nguồn Node đích và node lân cận phải qua. Thƣ mục đƣợc lƣu lại ở bộ điều khiển trung tâm mạng. Một kỹ thuật tìm đƣờng đơn giản khác là tìm đƣờng động, Kỹ thuật này không yêu cầu bất kỳ thông tin nào của mạng và nó làm việc nhƣ sau: Gói gửi từ một nguồn đến mọi Node lân cận. ở tại mỗi node đến, gói vừa mới đến lại chuyển đi trên trên mọi đƣờng ra, ngoài đƣờng nó đến, và cứ tiếp tục nhƣ vậy Trafic control là giá trị lƣu lƣợng trong mạng cần phải điều hoà để tăng hiệu suất và ổn định công suất. các phần tử của Traffic control..Traffic control có 4 loại với mục đích khác nhau: Flowcontrol, Congestion control, Deadlock control. Flow control liên quan đến việc điều chỉnh lƣu lƣợng của dữ liệu truyền giữa 2 điểm, cơ sở của Flow control là cho phép bộ thu với lƣu lƣợng sao cho không bị tràn. Điển hình của Flow control là thực hiện với một số loại kỹ thuật nhƣ cửa sổ trƣợt Congestion control là kiểm tra sự nghẽn mục đích là nắm đƣợc số của packet đƣợc đƣa vào mạng theo mức. Mạng chuyển mạch gói là là một mạng xếp hàng tại mỗi Node, các gói đƣợc xếp hàng để dƣa ra theo một đƣờng ra nào đó, nếu nhƣ số lƣợng các gói đến xếp hàng nhiều hơn nhiều hơn lƣợng các gói có thể truyền thì độ lớn của hàng càng phình ra, còn nếu nhƣ lƣợng các gói đến (tốc độ) ít hơn lƣợng gửi đi thì vấn dề xếp hàng không xảy ra và tốc độ đến bằng tốc độ truyền đi. Trên mỗi đƣờng có các gói đến hoặc đi. Ta có thể giả thiết rằng có 2 buffer cho mỗi đƣờng 1 dành cho các gói đến và 1 dành cho gói xếp hàng chuyển đi. Trong trƣờng hợp, gói đến nó đƣợc lƣu lại ở bộ nhớ đệm đến của đƣờng dây tƣơng ứng, Node kiểm tra gói đến và quyết định đƣờng đi và chuyển gói đó đến buffer ra thích hợp. gói đƣợc xếp hàng chờ đƣa ra với khả năng nhanh nhất, Nếu nhƣ gói đến quá nhanh so KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -13- với hoạt động của Node hoặc quá nhanh so với việc xoá trong bộ nhớ đệm ra thì đƣơng nhiên gói sẽ đến mà không đƣợc giữ lại và làm cho đƣờng truyền bị nghẽn. Deadlock control Một Node không chấp nhận chuyển tiếp các gói vì nó không có buffer để dùng Error control chức năng cuối cùng của chuyển mạch gói là kiểm tra sai có nhiều nguyên nhân dẫn đến sai, mất gói trong chuyển mạch gói đó là: Đƣờng nối hƣ, Node hƣ, Trạm thu nhận hƣ 1.5. Chuẩn hóa mô hình tham chiếu OSI (Open System Interconnection) 1.5.1 Kiến trúc phân tầng Để giảm độ phức tạp khi thiết kế và cài đặt mạng số liệu đƣợc thiết kế theo quan điểm kiến trúc 7 tầng nguyên tắc là: mỗi hệ thống trong một mạng đều có số lƣợng tầng là 7 chức năng của mỗi tầng là nhƣ nhau, xác định giao diện giữa 2 tầng kề nhau và giao thức giữa 2 tầng đồng mức của 2 hệ thống kết nối với nhau. Trên thực tế dữ liệu không đƣợc truyền trực tiếp từ tầng thứ i của hệ thống này sang tầng thứ i của hệ thống kia (trừ tầng thấp nhất trực tiếp sử dụng đƣờng truyền vật lý). Từ hệ thống gửi truyền sang hệ thống nhận theo quy trình nhƣ sau: Dữ liệu từ tầng i của hệ thống gửi sẽ đi từ tầng trên xuống tầng dƣới và tiếp tục đến tầng dƣới cùng – tầng vật lý qua đƣờng truyền vật lý chuyển đến hệ thống nhận và dữ liệu sẽ đi ngƣợc lên các tầng trên đến tầng đồng mức thứ i. Nhƣ vậy 2 hệ thống kết nối với nhau chỉ có tầng vật lý mới có kết nối vật lý còn các tầng khác chỉ có kết nối logic 1.5.2 Mô hình tham chiếu Mô hình OSI đƣợc hình thành vào năm 1974 bởi hội đồng các tiêu chuẩn đƣợc biết nhƣ tổ chức các tiêu chuẩn quốc tế (ISO). Mô hình này, nhƣ là mô hình liên kết các hệ thống mở, hoặc mô hình OSI, phân chia hệ thống thông tin thành 7 lớp. Mỗi lớp thực hiện một chức năng riêng biệt nhƣ một phần công việc để cho phép các chƣơng trình ứng dụng trên các hệ thống khác liên lạc, nếu nhƣ chúng đang hoạt động trên cùng một hệ thống. Mô hình OSI là một mô hình kiến trúc cơ bản. Mô hình không dành riêng cho phần mềm hoặc phần cứng nào. OSI miêu tả các chức năng của mỗi lớp nhƣng không cung cấp phần mềm hoặc thiết kế phần cứng để phục vụ cho mô hình này. Mục đích sau cùng của mô hình là cho khả năng hoạt động tƣơng lai của nhiều thiết bị truyền thông. Một thiết bị truyền thông có thể đƣợc thiết kế dựa trên mô hình này. Thông qua việc đề cập nhiều lần bởi các qui định của LAN, có một số dữ liệu và thông tin thoại đƣợc thiế t kế theo mô hình OSI. KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -14- Có 7 và chỉ 7 lớp tạo lên mô hình này (việc qui định các mức và các lớp có thể đƣợc sử dụng, hình 1.6 mô tả các lớp theo trình tự từ dƣới lên trên; Lớp vật lý (physical layer), lớp liên kết dữ liệu Data link layer), lớp mạng (Network layer), lớp vận chuyển (Transport layer), lớp tập hợp (Session layer), lớp trình bầy (presentation) và lớp ứng dụng (application layer). Mỗi lớp có một mục đích riêng và có chức năng độc lập của chúng. Hình 1.6. Mô hình OSI Physical layer: Lớp này định nghĩa các phƣơng pháp sử dụng để truyền và thu dữ liệu trên mạng, nó bao gồm: cáp, các thiết bị đƣợc sử dụng để kết nối bộ giao tiếp mạng của trạm tới cáp. Tín hiệu liên quan tới dữ liệu truyền/thu và khả năng xác định các lối dữ liệu trê phƣơng tiện mạng ( the cable plant). Datalink layer: lớp này đồng bộ hoá truyền dẫn và vận dụng điều khiển lối vào mức khung và phục hồi thông tin có thể truyền trên lớp vật lí. Khuôn dạng khung và CRC (kiểm tra vòng) đƣợc thực hiện tại các lớp vật lý. Lớp này thực hiện các phƣơng pháp truy nhập nhƣ Ethernet và Token Ring. Nó luôn cung cấp địa chỉ lớp vật lí cho khung truyền. Network layer: Lớp này điều khiển việc chuyển tiếp các thông báo giữa các trạm. Trên cơ sở một số thông tin, lớp này sẽ cho phép dữ liệu theo trình tự giữa hai trạm để hạn chế cho cả hai đƣờng logic và vật lí. Lớp này cho phép các khối dữ liệu đƣợc truyền tới các mạng khác thông qua việc sử dụng một số thiết bị đƣợc biết nhƣ router. Qua các router đƣợc định nghĩa tại lớp này. Transport layer: Lớp này cung cấp cho truyền dẫn end-to-end của dữ liệu ( trạm nguồn tới trạm đích). Nó cho phép dữ liệu đƣợc truyền một cách tin cậy, và đảm bảo rằng Application Presentation Session Transport Network Datalink Physical Ứng dụng Trình bày Phiên Vận chuyển Mạng Liên kết dữ liệu Vật lý KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -15- dữ liệu đƣợc truyền hoặc đƣợc thu không có lỗi, chính xác theo trình tự. Session layer: Lớp này thiết lập, duy trì và cắt đứt liên kết giữa hai trạm trên một mạng. Lớp này chịu trách nhiệm biên dịch địa chỉ tên trạm. Presentation layer: Lớp này thực hiện chuyển đổi cú pháp dữ liệu để đáp ứng yêu cầu truyền dữ liệu của các ứng dụng qua môi trƣờng OSI. Application layer: Lớp này đƣợc sử dụng cho các ứng dụng, đó là yếu tố để thực hiện trên mạng. Các ứng dụng nhƣ truyền file, thƣ điện tử ... Trên đây là những gì mà mô hình OSI đã thực hiện. Ngay sau khi mô hình OSI này ra đời thì nó đƣợc dùng làm có sở để nối các hệ thống mở phục vụ cho các ứng dụng phân tán. Từ “mở” ở đây nói lên khả năng hai hệ thống có thể kết nối để trao đổi thông tin với nhau, nếu chúng tuân thủ theo mô hình tham chiến và các chuẩn liên quan. Điều quan trọng nhất của mô hình OSI là đƣa ra các giải pháp cho vấn đề truyền thông giữa các trạm không giống nhau. Hai hệ thống dù khác nhau nhƣ thế nào đều có thể truyền thông với nhau nếu chúng bảo đảm những điều kiện sau: Chúng cài đặt cùng một tập các chức năng truyền thông. - Các chức năng đó đƣợc tổ chức thành một tập các tầng, các tầng đồng mức phải cung cấp các chức năng nhƣ nhau - Các tầng đồng mức phải sử dụng một giao thức chung Để bảo đảm bảo các điều kiện trên cần phải có các chuẩn. Các chuẩn phải xác định các chức năng và dịch vụ của tầng. Các chuẩn cũng phải xác định các giao thức giữa các tầng đồng mức. Mô hình OSI 7 lớp chính là cơ sở để xây dựng các chuẩn đó. 1.5.3. Phương thức hoạt động Ơ mỗi tầng trong mô hình OSI có 2 phƣơng thức hoạt động: phƣơng thức có liên kết (connection oriented) và phƣơng thức không liên kết (connectionless) Với phƣơng thức có liên kết trƣớc khi truyền dữ liệu cần thiết lập một liên lết logic giữa các thực thể đồng mức. nhƣ vậy quá trình truyền thông gồm 3 giai đoạn: - Thiết lập liên kết logic: 2 thực thể đồng mức ở 2 hệ thống sẽ thƣơng lƣợng với nhau về các thông số sẽ sử dụng trong giai đoạn sau - Truyền dữ liệu : Dữ liệu sẽ đƣợc truyền với cơ chế kiểm soát và quản lý kèm theo (nhƣ kiểm soát lỗi , kiểm soát luồng, cắt/hợp dữ liệu) - Huỷ bỏ liên kết : giải phóng các tài nguyên hệ thống đã đƣợc cấp phát cho liên kết để dùng cho các liên kết khác Mỗi giai đoạn trên thƣờng đƣợc thể hiện bằng một hàm tƣơng ứng. Thí dụ hàm connect thể hiện giai đoạn thiết lập liên kết, hàm Data thể hiện giai đoạn truyền dữ liệu và KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -16- hàm Disconnect thể hiện giai đoạn huỷ bỏ liên kết. Cùng với 4 hàm nguyên thuỷ trên cho mỗi giai đoạn ta sẽ có 12 thủ tục chính để xây dựng các dịch vụ và các giao thức chuẩn theo kiểu OSI. Còn đối với phƣơng thức không liên kết thì không cần thiết lập liên kết logic và mỗi đơn vị dữ liệu đƣợc truyền độc lập với các đơn vị dữ liệu trƣớc hoặc sau nó. Phƣơng thức này chỉ có duy nhất một giai đoạn truyền dữ liệu So sánh 2 phƣơng thức hoạt động trên thi phƣơng thức có liên kết cho phép truyền dữ liệu tin cậy, do đƣợc kiểm soát và quản lý chặt chẽ theo từng liên kết lôgic, nhƣng cài đặt khó khăn . Phƣơng thức không liên kết cho phép các PDU có thể đƣợc truyền đi theo nhiều đƣờng khác nhau để tới đích, thích nghi đƣợc với sự thay đổi trạng thái của mạng, nhƣng lại gặp phải khó khăn khi tập hợp lại các PDU để chuyển tới ngƣời dùng. Về nguyên tắc 2 tầng lân cận không nhất thiết phải dùng chung một phƣơng thức hoạt động. KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -17- Chƣơng 2. ĐỊNH TUYẾN TRONG MẠNG THÔNG TIN 2.1. YÊU CẦU VỀ ĐỊNH TUYẾN TRONG MẠNG THÔNG TIN 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.1 là một ví dụ của một graph. Hình 2.1. 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) KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -18- 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] ở đây 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 KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -19- 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. 2.2. CÁC MÔ HÌNH ĐỊNH TUYẾN QUẢNG BÁ (broadcast routing) 2.2.1 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ỏ. 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. - 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. KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -20- - 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õ rang nằm trên hƣớng sai. 2.2.2 Định tuyến bước 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. 2.2.3 Định tuyến khoai tây nóng (hot potato) Định tuyến riêng biệt là loại định tuyến mà router quyết đị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 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ảu thuật khoai tây nóng do đó sẽ đặt gói mới đến vào hàng chờ này. KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -21- Hình 2.1. Hàng chờ bên trong router 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. 2.2.4 Định tuyến nguồn (source routing) và mô hình cây (spanning tree) Chúng ta sẽ xét một số thuật toán cơ bản dùng cho việc tìm kiếm các cây đƣợc sử dụng để thiết kế và phân tích mạng. Một cây là một graph không có các vòng; bất kỳ một cặp nút nào cũng chỉ có duy nhất một đƣờng đi. ở đây chủ yếu xem xét các graph vô hƣớng, những graph đó có các liên kết đƣợc sử dụng cả hai chiều trong quá trình tạo ra các đƣờng đi. Vì một số lý do, các cây rất hữu dụng và đƣợc sử dụng nhƣ là graph cơ bản cho các thuật toán và các kỹ thuật phân tích và thiết kế mạng. Thứ nhất, các cây là mạng tối thiểu; cung cấp một sự kết nối mà không một liên kết nào là không cần thiết. Thứ hai, do việc chỉ cung cấp duy nhất một đƣờng đi giữa một cặp nút bất kỳ, các cây giải quyết các vần đề về định tuyến (nghĩa là quyết định việc chuyển lƣu lƣợng giữa hai nút). Điều đó làm đơn giản mạng và dạng của nó. Tuy nhiên, vì các cây liên thông tối thiểu nên cũng đơn giản và có độ tin cậy tối thiểu. Đó là nguyên nhân tại sao các mạng thực tế thƣờng có tính liên thông cao hơn. Chính vì vậy, việc thiết kế một mạng thƣờng bắt đầu bằng một cây. 2.2.5 Duyệt cây Cho trƣớc một cây nào đó, chúng ta có thể đi tới mọi nút của nó. Quá trình đó gọi là một quá trình duyệt cây. Trong quá trình thực hiện, các cạnh trong cây đƣợc duyệt hai lần, mỗi lần theo một hƣớng khác nhau. Có nhiều cách duyệt khác nhau. Đầu tiên, chỉ ra một nút của cây làm nút gốc. Việc duyệt đƣợc thực hiện xoay quanh nút đó. Có một số điều kiện để lựa chọn nút gốc này (chẳng hạn nút gốc là một khu vực máy tính trung tâm). Ngoài ra, nút gốc có thể đƣợc chọn một cách ngẫu nhiên. Giả sử nút A trong hình 4.1 là nút gốc của cây. Từ A chúng ta có thể lần lƣợt đi tới các nút kề cận của nó nhƣ là B, C hoặc D. Sau đó, lại đi theo các nút kề cận của chúng (B, C và D) là E, F, G và H. Tiếp tục đi tới lần lƣợt các nút kề cận khác bên cạnh các nút này. Khi đó, việc duyệt này sẽ kết thúc khi tới các nút I, J, K và L. Quá trình này đƣợc gọi là tìm kiếm theo KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -22- chiều rộng. Trong quá trình tìm kiếm theo chiều rộng một đặc điểm cần chú ý là những nút gần nút gốc nhất sẽ đƣợc tới trƣớc. Việc tìm kiếm sẽ thực hiện theo mọi hƣớng cùng lúc. Điều đó đôi khi có ích và đƣợc thực hiện dễ dàng. Một thuật toán nhằm đi tới mọi nút của cây thì đƣợc gọi là thuật toán duyệt cây. Thuật toán sau đây, Bfstree, thực hiện một quá trình tìm kiếm theo chiều rộng. (Chúng ta quy ƣớc rằng, các tên hàm có ký tự đầu tiên là ký tự hoa để phân biệt chúng với các tên biến). Bfstree sẽ sử dụng một danh sách kề cận n_adj_list, danh sách này liệt kê tất cả các nút kề cận của mỗi nút thuộc cây. Để đơn giản hơn, giả sử rằng cây này là một cây hữu hƣớng hƣớng ra nhìn từ gốc và do đó n_adj_list sẽ chỉ bao gồm các nút kề cận với một nút nào đó mà các nút kề cận đó xa gốc hơn so với nút đang xét. Hình 2.2. Duyệt cây KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -23- void <-BfsTree ( n, root, n_adj_list ): dcl n_adj_list [n, list ] scan_queue [queue ] InitializeQueue (scan_queue ) Enqueue( root, scan_queue ) while (NotEmpty(scan_queue)) node <- Dequeue (scan_queue) Visit(node ) for each (neighbor , n_adj_list [node ]) Enqueue(neighbor, scan_queue) Visit là một thủ tục trong đó thực hiện một số quá trình nào đó đối với mỗi nút (chẳng hạn nhƣ in lên màn hình các thông tin của mỗi nút .v.v). Thuật toán này đƣợc thực hiện cùng một hàng đợi. Hàng đợi là một FIFO; trong đó các phần tử đƣợc thêm vào từ phía sau hàng đợi và chuyển ra từ phía trƣớc. Các thủ tục InitializeQueue, Enqueue, Dequeue, NotEmpty làm việc trên các hàng đợi. InitializeQueue thiết lập một hàng đợi rỗng. Enqueue, Dequeue là các thủ tục để thêm một phần tử vào cuối hàng đợi và chuyển một phần tử ra từ đầu hàng đợi. Hàm NotEmpty trả về TRUE hoặc FALSE tuỳ thuộc vào hàng đợi có rỗng hay không. n_adj_list là một chuỗi mà mỗi phần tử của chuỗi là một danh sách. n_adj_list[n] là một danh sách các nút kề cận nút n. Nhƣ đã nói ở chƣơng trƣớc, for_each(element, list), là một cấu trúc điều khiển thực hiện vòng lặp đối với tất cả các phần tử của list và thực hiện các mã ở bên trong vòng lặp, trong vòng lặp đó các phần tử của list lần lƣợt đƣợc sử dụng. Thủ tục trên hoạt động với giả thiết là n_adj_list đã đƣợc thiết lập trƣớc khi thủ tục BfsTree đƣợc gọi. Tƣơng tự, ta có thể định nghĩa một quá trình tìm kiếm theo chiều sâu. Quá trình này cũng bắt đầu từ nút gốc. Quá trình duyệt tiếp tục thực hiện nút láng giềng chƣa đƣợc duyệt của nút vừa mới đƣợc duyệt. Ta cũng giả sử rằng cây bao gồm các liên kết có hƣớng đi ra xa nút gốc. Ví dụ 2.1: Trở lại với graph trong hình 4.1, ta có thể tới nút B từ nút A. Sau đó, ta tới nút E, kề cận với nút B-nút đƣợc duyệt gần thời điểm hiện tại nhất. Nút E này không có nút kề cận chƣa duyệt nào, do vậy ta phải quay trở lại nút B để đi sang nút F. Ta tiếp tục đi tới các nút I, J, K (cùng với việc quay lại nút I), và nút L. Sau đó ta quay trở về nút A, tiếp tục tới các nút còn lại là C, D, G và H. Do vậy, toàn bộ quá trình duyệt là: A, B, E, F, I, J, K, L, C, D, G, H KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -24- Nhớ rằng thứ tự của quá trình duyệt là không duy nhất. Trong quá trình duyệt trên ta chọn các nút kề cận để xâm nhập theo thứ tự từ trái qua phải. Nếu chọn theo thứ tự khác, quá trình duyệt là: A, B, F, I, J, K, L, E, D, H, G, C Trật tự thực tế của quá trình duyệt phụ thuộc vào từng thuật toán cụ thể. Điều này cũng đúng với một quá trình tìm kiếm theo chiều rộng. Kiểm tra thuật toán BfsTree, trật tự này là một hàm của trật tự các nút cận kề trong n_adj_list. Thuật toán DfsTree sau sẽ thực hiện một quá trình tìm kiếm theo chiều sâu. void <- DfsTree(n, root, n_adj_list): dcl n_adj_list [n, list] Visit(root) for each(neighbor, n_adj_list[node]) DfsTree(n, neighbor, n_adj-list) Quá trình tìm kiếm này sẽ đƣợc thực hiện với sự trợ giúp của một ngăn xếp theo kiểu LIFO, nghĩa là phần tử đƣợc thêm vào và chuyển ra từ đỉnh ngăn xếp. Trong trƣờng hợp này, chúng ta thƣờng gọi đệ quy DfsTree, thực tế chúng ta đã sử dụng ngăn xếp hệ thống, nghĩa là sử dụng loại ngăn xếp mà hệ thống sử dụng để lƣu giữ các lời gọi hàm và đối số. Cả hai loại duyệt trình bày ở trên đều là quá trình duyệt thuận (nghĩa là các quá trình này duyệt một nút rồi sau đó duyệt tới nút tiếp theo của nút đó). Quá trình duyệt ngƣợc đôi khi cũng rất cần thiết, trong quá trình duyệt ngƣợc một nút đƣợc duyệt sau khi đã duyệt nút tiếp của nút đó. Dĩ nhiên, cũng có thể thành lập một danh sách thuận và sau đó đảo ngƣợc danh sách đó. Cũng có thể thay thế trật tự tìm kiếm một cách trực tiếp nhƣ thủ tục sau: void <- PostorderDfsTree(n, root, n_adj_list): dcl n_adj_list [n, list] for each(neighbor, n_adj_list[node]) PostorderDfsTree(n, neighbor, n_adj_list) Visit (root) a. Các thành phần liên thông trong các graph vô hƣớng Ta có thể áp dụng khái niệm duyệt các nút vào một graph vô hƣớng, đơn giản chỉ bằng cách theo dõi các nút đã đƣợc duyệt và sau đó không duyệt các nút đó nữa. Có thể duyệt một graph vô hƣớng nhƣ sau: KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -25- void <- Dfs(n, root, n_adj_list): dcl n_adj_list [n, list] visited [n] void <- DfsLoop (node) if (not(visited [node]) visited [node]<-TRUE visit [node] for each(neighbor, n_adj_list[node]) DfsLoop (neighbor) visited <-FALSE DfsLoop (root) Chú ý rằng câu lệnh Visited <-FALSE dùng khởi tạo toàn bộ các phần tử mảng đƣợc duyệt bằng FALSE. Cũng cần chú ý rằng thủ tục DfsLoop đƣợc định nghĩa bên trong thủ tục Dfs nên DfsLoop có thể truy cập tới visited và n_adj_list (Lƣu ý rằng cách dễ nhất để đọc các giả mã cho các hàm có dạng hàm Dfs ở trên là trƣớc tiên hãy đọc thân của hàm chính rồi quay trở lại đọc thân của các hàm nhúng nhƣ hàm DfsLoop). Chú ý rằng trong quá trình duyệt chúng ta đã ngầm kiểm tra tất cả các cạnh trong graph, một lần cho mỗi đầu cuối của mỗi cạnh. Cụ thể, với mỗi cạnh (i, j) của graph thì j là một phần tử của n_adj_list[i] và i là một thành phần trong n_adj_list[j]. Thực tế, có thể đƣa chính các cạnh đó vào các danh sách kề cận của nó và sau đó tìm nút ở điểm cuối khác của cạnh đó bằng hàm: node <- OtherEnd(node1, edge) Hàm này sẽ trả về một điểm cuối của edge khác với node1. Điều đó làm phức tạp quá trình thực hiện đôi chút. Có thể dễ dàng thấy rằng độ phức tạp của các thuật toán duyệt cây này bằng O(E), với E là số lƣợng cạnh trong graph. Bây giờ chúng ta có thể tìm đƣợc các thành phần liên thông của một graph vô hƣớng bằng cách duyệt mỗi thành phần. Chúng ta sẽ đánh dấu mỗi nút bằng một chỉ số thành phần khi chúng ta tiến hành. Các biến n_component sẽ theo dõi bất kỳ thành phần nào mà chúng ta đi tới KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -26- void <- LabelComponent (n, n_adj_list): dcl n_component_number [n], n_adj_list[n,list] void <- Visit [node] n_component_number [node]<- ncomponents n_component_number<-0 ncomponent<-0 for each(node, node_set) if (n_component_number [node]=0) ncomponent +=1 Dfs (node, n_adj_list) Chúng ta định nghiã một hàm Visit để thiết lập một chỉ số thành phần các nút đƣợc duyệt. Hàm này nằm bên trong thủ tục LabelComponent và chỉ có thể đƣợc gọi từ trong thủ tục đó. Mặt khác, Dfs còn đƣợc định nghĩa ở bên ngoài, vì thế nó có thể đƣợc gọi từ bất kỳ đâu. Trong khi thực hiện quá trình duyệt theo chiều rộng và chiều sâu một graph vô hƣớng, những cạnh nối một nút với một nút láng giềng chƣa duyệt trƣớc khi duyệt nút đó tạo ra một cây, nếu graph là không liên thông thì tạo ra một rừng. Hình 2.3. Các thành phần Hình2.3 biểu diễn một graph có 4 thành phần. Giả sử vòng trên tập các nút đi theo tuần tự alphabet, các thành phần đƣợc đánh số theo trật tự các nút có chữ cái "thấp nhât" và chỉ số thành phần đƣợc biểu diễn ở bên cạnh nút. Với mỗi thành phần, thuật toán trên sẽ gọi Dfs để kiểm tra thành phần đó. Trong đó, thuật toán cũng kiểm tra các cạnh, mỗi cạnh một lần. Vì thế, độ phức tạp của nó có bậc bằng bậc của KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -27- tổng số các nút cộng với số các cạnh trong tất cả các thành phần (nghĩa là độ phức tạp của thuật toán bằng O(N+E)). b. Cây bắc cầu tối thiểu (Minimum Spanning Tree) Có thể sử dụng Dfs để 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. Nhƣ đã giải thích ở trên, Dfs 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.  Thuật toán "háu ăn" Một cách tiếp cận khả dĩ để tìm một cây có tổng độ dài tối thiểu là, ở mỗi giai đoạn của thuật toán, lựa chọn cạnh ngắn nhất có thể. Thuật toán đó gọi là thuật toán "háu ăn". Thuật toán này có tính chất "thiển cận" nghĩa là không lƣờng trƣớc đƣợc các kết quả cuối cùng do các quyết định mà chúng đƣa ra ở mỗi bƣớc gây ra. Thay vào đó, chúng chỉ đƣa ra cách chọn tốt nhất cho mỗi quá trình lựa chọn. Nói chung, thuật toán "háu ăn" không tìm đƣợc lời giải tối ƣu cho một bài toán. Thực tế thuật toán thậm chí còn không tìm đƣợc một lời giải khả thi ngay cả khi lời giải đó tồn tại. Tuy nhiên chúng hiệu quả và dễ thực hiện. Chính vì vậy chúng đƣợc sử dụng rộng rãi. Các thuật toán này cũng thƣờng tạo cơ sở cho các thuật toán có tính hiệu quả và phức tạp hơn. KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -28- Vì thế, câu hỏi đầu tiên đặt ra khi xem xét việc ứng dụng một thuật toán để giải quyết một bài toán là liệu bài toán ấy có hay không cấu trúc nào đó đảm bảo cho thuật toán hoạt động tốt. Hy vọng rằng thuật toán ít ra cũng đảm bảo đƣợc một lời giải khả thi nếu lời giải đó tồn tại. Khi đó, nó sẽ đảm bảo tính tối ƣu và đảm bảo yêu cầu nào đó về thời gian thực hiện. Bài toán tìm các cây bắc cầu tối thiểu thực sự có một cấu trúc mạnh cho phép thuật toán "háu ăn" đảm bảo cả tính tối ƣu cũng nhƣ đảm bảo độ phức tạp tính toán ở mức độ vừa phải. Dạng chung của thuật toán "háu ăn" là: Bắt đầu bằng một lời giải rỗng s. Trong khi vẫn còn có các phần tử cần xét Tìm e, phần tử "tốt nhất" vẫn chƣa xét Nếu việc thêm e vào s là khả thi thì e đƣợc thêm vào s, nếu việc thêm đó không khả thi thì loại bỏ e. Các yêu cầu các khả năng sau:  So sánh giá trị của các phần tử để xác định phần tử nào là "tốt nhất"  Kiểm tra tính khả thi của một tập các phần tử Khái niệm "tốt nhất" liên quan đến mục đích của bài toán. Nếu mục đích là tối thiểu, "tốt nhất" nghĩa là bé nhất. Ngƣợc lại, "tốt nhất" nghĩa là lớn nhất. Thƣờng thƣờng, mỗi giá trị gắn liền với một phần tử, và giá trị gắn liền với một tập đơn giản chỉ là tổng các giá trị đi cùng của các phần tử trong tập đó. Đó là trƣờng hợp cho bài toán cây bắc cầu tối thiểu đƣợc xét trong phần này. Tuy nhiên, đó không phải là trƣờng hợp chung. Chẳng hạn, thay cho việc tối thiểu tổng độ dài của tất cả các cạnh trong một cây, mục đích của bài toán là tối thiểu hoá độ dài các cạnh dài nhất trong cây. Trong trƣờng hợp đó, giá trị của một cạnh là độ dài của cạnh đó và giá trị của một tập sẽ là độ dài của cạnh dài nhất nằm trong tập. Muốn tìm đƣợc cạnh "tốt nhất" để bổ sung, hãy đánh giá các cạnh theo độ ảnh hƣởng về giá trị của nó tới giá trị của tập. Giả sử V(S) là giá trị của tập S và v(e,S) là giá trị của một phần tử e thì v(e,S) có quan hệ với tập S bởi công thức v(e,S)= V(S  e) - V(S) Trong trƣờng hợp tối thiểu độ dài của cạnh dài nhất trong một cây. v(e,S) bằng 0 đối với bất kỳ cạnh nào không dài hơn cạnh dài nhất đã đƣợc chọn. Ngƣợc lại, nó sẽ bằng hiệu độ dài giữa cạnh với cạnh dài nhất đã đƣợc chọn, khi hiệu đó lớn hơn 0. Trong trƣờng hợp chung, giá trị của tập có thể thay đổi một cách ngẫu nhiên khi các phần tử đƣợc bổ sung vào nó. Chúng ta có thể gán giá trị 1 cho các tập có số lƣợng phần tử là chẵn và 2 cho các tập có số lƣợng phần tử là lẻ. Điều đó làm cho các giá trị của các phần tử chỉ là một KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -29- trong hai giá trị +1 và -1. Trong trƣờng hợp này, thuật toán "háu ăn" không đƣợc sử dụng. Bây giờ giả sử rằng "trọng lƣợng" của một tập biến đổi theo một cách hợp lý hơn thì khi đó, sẽ có một cơ sở hợp lý hơn cho việc chỉ ra phần tử "tốt nhất". Một điều quan trọng cần chú ý đó là, khi tập lớn lên, giá trị của phần tử mà trƣớc đó không đƣợc xem xét có thể thay đổi do các phần tử thêm vào tập đó. Khi điều này xảy ra, thuật toán "háu ăn" có thể mắc lỗi trong các lựa chọn của nó và sẽ ảnh hƣởng tới chất lƣợng của lời giải mà chúng ta nhận đƣợc. Tƣơng tự, trong hầu hết các trƣờng hợp, tính khả thi có thể bị ảnh hƣởng một cách ngẫu nhiên do sự bổ sung phần tử. Chính vì vậy, trong các bài toán mà những tập có số lƣợng phần tử chẵn có thể đƣợc xem là khả thi và những tập có số phần tử là lẻ có thể đƣợc xem là không khả thi thì thuật toán "háu ăn" hoặc bất kỳ thuật toán nào có bổ sung các phần tử, mỗi lần một phần tử, sẽ không hoạt động. Vì vậy chúng ta sẽ giả thiết các tính chất sau, những tính chất này luôn đƣợc duy trì trong mọi trƣờng hợp xem xét: Tính chất 1: Bất kỳ một tập con nào của một tập khả thi thì cũng khả thi, đặc biệt tập rỗng cũng là một tập khả thi. Ngoài ra giả thiết rằng độ phức tạp của thuật toán để tính toán giá trị của một tập và kiểm tra sự khả thi của chúng là vừa phải, đặc biệt, khi độ phức tạp này là một đa thức của số nút và cạnh trong graph. list<-Greedy (properties) dcl properties [list, list] candidate_set[list] solution[list] void<-GreedyLoop ( *candidate_set, *solution) dcl test_set[list],solution[list], candidate_set[list] element <- SelectBestElement(candidate_set) test_set <-Append(element,solution) if(Test(test_set)) solution<-test_set candidate_set<-Delete(element,candidate_set) if(not(Empty(candidate_set))) Greedy_loop(*candidate_set, *solution) candidate_set<-ElementsOf(properties) KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -30- solution<- if(!(Empty(element_set))) GreedyLoop(*candidate_set, *solution) return(solution) Bây giờ ta đã có thể xem xét sâu hơn các câu lệnh của thuật toán "háu ăn". Các câu lệnh của thuật toán hơi khó hiểu vì chúng dựa trên định nghĩa của hai hàm, Test và SelestBestElement (là hàm kiểm tra tính khả thi và đánh giá các tập). Chúng ta cũng giả sử rằng có một cấu trúc properties, là một danh sách của các danh sách chứa tất cả các thông tin cần thiết để kiểm tra và đánh giá tất cả các tập. Một danh sách của các danh sách đơn giản chỉ là một danh sách liên kết, mà mỗi thành viên của nó là một danh sách. Thậm chí cấu trúc đó có thể đƣợc lồng vào nhau sâu hơn, nghĩa là có các danh sách nằm bên trong các danh sách nằm bên trong các danh sách. Cấu trúc nhƣ vậy tƣơng đối phổ biến và có thể đƣợc sử dụng để biểu diễn hầu hết các kiểu thông tin. Có thể lƣu giữ độ dài, loại liên kết, dung lƣợng, hoặc địa chỉ. Bản thân các mục thông tin này có thể là một cấu trúc phức tạp; nghĩa là cấu trúc đó có thể lƣu giữ giá và các dung lƣợng của một vài loại kênh khác nhau cho mỗi liên kết. Trên thực tế, điều đó rất có ích cho việc duy trì các cấu trúc dữ liệu trợ giúp để cho phép thuật toán thực hiện hiệu quả hơn. Bài toán về cây bắc cầu tối thiểu là một ví dụ. Tuy nhiên, để rõ ràng, giả sử rằng tất cả quá trình tính toán đƣợc thực hiện trên một cấu trúc properties sẵn có (đã đƣợc khởi tạo).  đƣợc sử dụng để biểu diễn tập rỗng. Append và Delete là các hàm bổ sung và chuyển đi một phần tử khỏi một danh sách. ElementsOf chỉ đơn giản để chỉ ra các phần tử của một danh sách; vì vậy, ban đầu tất cả các phần tử trong properties là các ứng cử. Có rất nhiều cách thực hiện các quá trình này. properties có thể là một dãy và các hàm Append, Delete và ElementsOf có thể hoạt động với các danh sách chỉ số (danh sách mà các phần tử là các chỉ số mạng). Trong thực tế cách thực hiện đƣợc chọn là cách làm sao cho việc thực hiện các hàm Test và SelectBestElement là tốt nhất. Đoạn giả mã trên giả thiết rằng thuật toán "háu ăn" sẽ dừng lại khi không còn phần tử nào để xem xét. Trong thực tế, có nhiều nguyên nhân để thuật toán dừng lại. Một trong những nguyên nhân là khi kết quả xấu đi khi các phần tử đƣợc tiếp tục thêm vào. Điều nay xảy ra khi tất cả các phần tử còn lại đều mang giá trị âm trong khi chúng ta đang cố tìm cho một giá trị tối đa. Một nguyên nhân khác là khi biết rằng không còn phần tử nào ở trong tập ứng cử có khả năng kết hợp với các phần tử vừa đƣợc chọn tạo ra một lời giải khả thi. Điều này xảy ra khi một cây bắc cầu toàn bộ các nút đã đƣợc tìm thấy. Giả sử rằng thuật toán dừng lại khi điều đó là hợp lý, còn nếu không, các phần tử không liên quan sẽ bị loại ra khỏi lời giải. KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -31- Giả thiết rằng, các lời giải cho một bài toán thoả mãn tính chất 1 và giá trị của tập đơn giản chỉ là tổng các giá trị của các phần tử trong tập. Ngoài ra, giả thiết thêm rằng tính chất sau đƣợc thoả mãn: Tính chất 2: Nếu hai tập Sp và Sp+1 lần lƣợt có p và p+1 phần tử là các lời giải và tồn tại một phần tử e thuộc tập Sp+1 nhƣng không thuộc tập Sp thì Sp{e} là một lời giải. Chúng ta thấy rằng, các cạnh của các rừng thoả mãn tính chất 2, nghĩa là nếu có hai rừng, một có p cạnh và rừng kia có p+1 thì luôn tìm đƣợc một cạnh thuộc tập lớn hơn mà việc thêm cạnh đó vào tập nhỏ hơn không tạo ra một chu trình. Một tập các lời giải thoả mãn các tính chất trên gọi là một matroid. Định lý sau đây là rất quan trọng (chúng ta chỉ thừa nhận chứ không chứng minh). Định lý 2.1 Thuật toán “háu ăn” đảm bảo đảm một lời giải tối ƣu cho một bài toán khi và chỉ khi các lời giải đó tạo ra một matroid. Có thể thấy rằng, tính chất 1 và tính chất 2 là điều kiện cần và đủ để đảm bảo tính tối ƣu của thuật toán “háu ăn” . Nếu có một lời giải cho một bài toán nào đó mà nó thoả mãn hai tính chất 1 và 2 thì cách đơn giản nhất là dùng thuật toán “háu ăn” để giải quyết nó. Điều đó đúng với một cây bắc cầu. Sau đây là một định lý không kém phần quan trọng. Định lý 2.2 Nếu các lời giải khả thi cho một bài toán nào đó tạo ra một matroid thì tất cả các tập khả thi tối đa có số lƣợng phần tử nhƣ nhau. Trong đó, một tập khả thi tối đa là một tập mà khi thêm các phần tử vào thì tính khả thi của nó không đƣợc bảo toàn; Nó không nhất thiết phải có số lƣợng phần tử tối đa cũng nhƣ không nhất thiết phải có trọng lƣợng lớn nhất. Định lý đảo của định lý trên cũng có thể đúng nghiã là nếu tính chất 1 đƣợc thoả mãn và mọi tập khả thi tối đa có cùng số lƣợng phần tử, thì tính chất 2 đƣợc thoả mãn. Định lý 2.2 cho phép chúng ta chuyển đổi một bài toán tối thiểu P thành một bài toán tối đa P' bằng cách thay đổi các giá trị của các phần tử. Giả thiết rằng tất cả v(xj) trong P có giá trị âm. Lời giải tối ƣu cho bài toán P có số lƣợng phần tử tối đa là m thì chúng ta có thể tạo ra một bài toán tối đa P' từ P bằng cách thiết lập các giá trị của các phần tử trong P' thành -v(xj). Tất cả các phần tử đều có giá trị dƣơng và P' có một lời giải tối ƣu chứa m phần tử. Thực ra, thứ tự của các lời giải tối đa phải đƣợc đảo lại: lời giải có giá trị tối đa trong P' cũng là lời giải có giá trị tối thiểu trong P. KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -32- Giả sử lúc nay ta cần tìm một lời giải có giá trị tối thiểu, tuân theo điều kiện là có số lƣợng tối đa các phần tử. Sẽ tính cả các phần tử có giá trị dƣơng. Có thể giải quyết bài toán P nhƣ là một bài toán tối đa P' bằng cách thiết lập các giá trị của các phần tử thành B-v(xj) với B có giá trị lớn hơn giá trị lớn nhất của xj. Khi đó các giá trị trong P' đều dƣơng và P' là một lời giải tối ƣu có m phần tử. Thứ tự của tất cả các tập khả thi tối đa đã bị đảo ngƣợc: một tập có giá trị là V trong P thì có giá trị là mB-V trong lời giải P'. Một giá trị tối đa trong P' thì có giá trị tối thiểu trong P. Quy tắc này cũng đúng với các cây bắc cầu thoả mãn tính chất 1 và tính chất 2 và có thể tìm một cây bắc cầu tối thiểu bằng cách sử dụng một thuật toán “háu ăn”. a. Thuật toán Kruskal Thuật toán Kruskal là một thuật toán “háu ăn” đƣợc sử dụng để tìm một cây bắc cầu tối thiểu. Tính đúng đắn của thuật toán dựa trên các định lý sau: Định lý 2.3 Các rừng thì thoả mãn tính chất 1 và 2. Nhƣ chúng ta đã biết, một rừng là một tập hợp các cạnh mà tập hợp đó không chứa các chu trình. Rõ ràng là bất kỳ một tập con các cạnh nào của một rừng (thậm chí cả tập rỗng) cũng là một rừng, vì vậy tính chất 1 đƣợc thoả mãn. Để thấy rằng tính chất 2 cũng thoả mãn, xét một graph đƣợc biểu diễn trong hình 2.4. Hình 2.3. xét một graph được biểu diễn trong hình 4.4. Giả sử có một rừng F1 có p cạnh. Rừng {2,4} là một ví dụ với p=2, và nó đƣợc biểu diễn bằng nét đứt trong hình 4.4. Khi đó xét một rừng khác F2 có p+1 cạnh. Có hai trƣờng hợp đƣợc xét. Trƣờng hợp 1: F2 đi tới một nút n, nhƣng F1 không đi tới nút đó. Một ví dụ của trƣờng hợp này là rừng {1, 4, 6}, rừng này đi tới E còn F1 thì không. Trong trƣờng hợp này, có thể tạo ra rừng {2, 4, 6} bằng cách thêm cạnh 6 vào rừng {2,4}. KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -33- Trƣờng hợp 2: F2 chỉ đi tới các nút mà F1 đi tới. Một ví dụ của trƣờng hợp này là rừng {1. 4. 5}. Xét S, một tập các nút mà F1 đi tới. Cho rằng có k nút trong tập S. Vì F1 là một rừng nên mỗi cạnh trong F1 giảm số lƣợng thành phần trong S đi một, do đó tổng số lƣợng thành phần là k-p. Tƣơng tự, F2 tạo ra k-(p+1) thành phần từ S (số lƣợng thành phần vừa nói bé hơn với số lƣợng thành phần của F1). Vì vậy, một cạnh tồn tại trong F2 mà các điểm cuối của nó nằm ở các thành phần khác nhau trong F1 thì có thể thêm cạnh đó vào F1 mà không tạo ra một chu trình. Cạnh 3 là một cạnh có tính chất đó trong ví dụ này (cạnh 1 và 5 cũng là những cạnh nhƣ vậy). Vì thế, chúng ta thấy rằng nếu tính chất 1 và 2 đƣợc thoả mãn thì một thuật toán “háu ăn” có thể tìm đƣợc một lời giải tối ƣu cho cả bài toán cây bắc cầu tối thiểu lẫn bài toán cây bắc cầu tối đa. Chú ý rằng một cây bắc cầu là một rừng có số cạnh tối đa N-1 cạnh với N là số nút trong mạng. Sau đây chúng ta sẽ xét bài toán tối thiểu. Thuật toán Kruskal thực hiện việc sắp xếp các cạnh với cạnh đầu tiên là cạnh ngắn nhất và tiếp theo chọn tất cả các cạnh mà những cạnh này không cùng với các cạnh đƣợc lựa chọn trƣớc đó tạo ra các chu trình. Chính vì thế, việc thực hiện thuật toán đơn giản là: list <- kruskal_l( n, m, lengths ) dcl length[m], permutation[m], solution[list] permution <- VectorSort( n , lengths ) solution <-  for each ( edge , permutation ) if ( Test(edge , solution ) ) solution <- Append ( edge , solution ) return( solution ) VectorSort có đầu vào là một vector có độ dài là n và kết quả trả về là thứ tự sắp xếp các số nguyên từ 1 tới n. Sự sắp xếp đó giữ cho giá trị tƣơng ứng trong vector theo thứ tự tăng dần. Ví dụ 2.2: Giả sử rằng n= 5 và giá trị của một vector là 31, 19, 42, 66, 27 VectorSort sẽ trả về thứ tự sắp xếp nhƣ sau: 2, 5, 1, 3, 4 Test nhận một danh sách các cạnh và trả về giá trị TRUE nếu các cạnh đó không chứa một chu trình. Vì Test đƣợc gọi cho mỗi nút, sự hiệu quả của toàn bộ thuật toán tuỳ thuộc vào tính hiệu quả của việc thực hiện Test. Nếu mỗi khi các cạnh đƣợc thêm vào cây, chúng ta theo dõi KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -34- đƣợc các nút của cạnh thuộc các thành phần nào thì Test trở nên đơn giản; đó đơn giản chỉ là việc kiểm tra xem các nút cuối của các cạnh đang đƣợc xét có ở cùng một thành phần không. Nếu cùng, cạnh sẽ tạo ra một chu trình. Ngƣợc lại, cạnh đó không tạo nên chu trình. Tiếp đó là xem xét việc duy trì cấu trúc thành phần. Có một số cách tiếp cận. Một trong các cách đó là ở mỗi nút duy trì một con trỏ đến một nút khác trong cùng một thành phần và có một nút ở mỗi thành phần gọi là nút gốc của thành phần thì trỏ vào chính nó. Vì thế lúc đầu, bản thân mỗi nút là một thành phần và nó trỏ vào chính nó. Khi một cạnh đƣợc thêm vào giữa hai nút i và j, trỏ i tới j. Sau đó, khi một cạnh đƣợc thêm vào giữa một nút i trong một thành phần có nút gốc là k và một nút j trong một thành phần có nút gốc là l thì trỏ k tới l. Vì vậy, chúng ta có thể kiểm tra một cạnh bằng cách dựa vào các con trỏ từ các nút cuối của nó và xem rằng chúng có dẫn đến cùng một nơi hay không. Chuỗi các con trỏ càng ngắn, việc kiểm tra càng dễ dàng. Nhằm giữ cho các chuỗi các con trỏ đó ngắn, Tarjan gợi ý nên làm gọn các chuỗi khi chúng đƣợc duyệt trong quá trình kiểm tra. Cụ thể, ông gợi ý một hàm FindComponent đƣợc tạo ra nhƣ sau: index <- FindComponent(node , *next) dcl next[] p=next[node] q=next[p] while ( p!=q ) next[node]= q node = q p=next[node] q=next[p] return (p) FindComponent trả về nút gốc của thành phần chứa node. Hàm này cũng điều chỉnh next , nút hƣớng về nút gốc chứa nút đó. Đặc biệt, hàm này điều chỉnh next hƣớng tới điểm ở tầng cao hơn. Tarjan chỉ ra rằng, bằng cách đó, thà làm gọn đƣờng đi tới nút gốc một các hoàn toàn còn hơn là không làm gọn một chút nào cả và toàn bộ kết quả trong việc tìm kiếm và cập nhật next chỉ lớn hơn so với O(n+m) một chút với n là số lƣợng nút và m là số lƣợng cạnh đƣợc kiểm tra. Ví dụ 2.3: KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -35- Hình 2.4. Phép tính Minimum Spanning Tree (MST) Xét một mạng đƣợc biểu diễn trong hình 4.4. các dấu * trong hình đƣợc giải thích dƣới đây. Đầu tiên, sắp xếp các cạnh và sau đó lần lƣợt xem xét từng cạnh, bắt đầu từ cạnh nhỏ nhất. Vì thế, chúng ta xem (A, C) là cạnh đầu tiên. Gọi FindComponent cho nút A ta thấy cả p lẫn q đều là A nên FindComponent trả về A nhƣ là nút gốc của thành phần chứa nút A. Tƣơng tự, FindComponent trả về C nhƣ là nút gốc của thành phần chứa nút C. Vì thế, chúng ta mang A và C vào cây và thiết lập next[A] bằng C. Sau đó, xét (B, D). Hàm cũng thực hiện tƣơng tự và B, D đƣợc thêm vào cây, next[B] bằng D. Chúng ta xét (C, E), chấp nhận nó và thiết lập next[C] bằng E. Bây giờ, xét (A, E). Trong FindComponent, p là C còn q là E. Vì thế chúng ta chạy vào vòng lặp while , thiết lập next[A] bằng E và rút ngắn đƣờng đi từ A tới E với E là nút gốc của thành phần chứa chúng. Node, p và q đƣợc thiết lập thành E và FindComponent trả về E nhƣ là nút gốc của thành phần chứa nút A. FindComponent cũng trả về E nhƣ là nút gốc của thành phần chứa E. Vì thế, cả hai điểm cuối của (A, E) là cùng một thành phần nên (A, E) bị loại bỏ. Tiếp đến, xét (A, B). Trong quá trình gọi FindComponent đối với nút A, chúng ta thấy rằng p=q=E và next không thay đổi. Tƣơng tự, quá trình gọi FindComponent đối với nút B ta đƣợc p=q=D. Vì thế, chúng ta thiết lập next[E] bằng D. Chú ý rằng, chúng ta không thiết lập next[A] bằng B, mà lại thiết lập next đối với nút gốc của thành phần của A bằng với nút gốc của thành phần của B. Cuối cùng, (C, D) đƣợc kiểm tra và bị loại bỏ. Trong hình 2.4 những cạnh trong cây bắc cầu đƣợc phân biệt bởi một dấu * ở ngay bên cạnh các cạnh đó. Nội dung các next đƣợc chỉ ra bằng các cung (các cạnh hữu hƣớng) có mũi tên. Chẳng hạn, next[B] bằng D đƣợc chỉ ra bằng một mũi tên từ B tới D. Chú ý rằng, các cung đƣợc định nghĩa bởi next tạo ra một cây, nhƣng nói chung cây đó không phải là một cây bắc cầu tối thiểu. Thực vậy, với trƣờng hợp có một cung (E, D), ngay cả khi các cung đó không cần thiết phải là một phần graph. Vì vậy, bản thân next chỉ định nghĩa cấu trúc thành phần khi KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -36- tiến hành thực hiện thuật toán. Chúng ta tạo một danh sách hiện các cạnh đƣợc chọn dành cho việc bao gộp trong cây. Giá của cây đƣợc định nghĩa bởi next tƣơng đối bằng phẳng, nghiã là các đƣờng đi tới các nút gốc của các thành phần là ngắn khiến FindComponent hoạt động hiệu quả. Hiển nhiên, sự phức tạp của thuật toán Kruskal đƣợc quyết định bởi việc sắp xếp các cạnh, sự sắp xếp đó có độ phức tạp là O(m log m). Nếu có thể tìm đƣợc cây bắc cầu trƣớc khi phải kiểm tra tất cả các cạnh thì chúng ta có thể cải tiến quá trình đó bằng cách thực hiện sắp xếp phân đoạn. Cụ thể, chúng ta có thể lƣu giữ các cạnh trong một khối (heap) và sau đó lấy ra, kiểm tra mỗi cạnh cho đến khi một cây đƣợc tạo ra. Chúng ta dễ dàng biết đƣợc quá trình đó dừng vào lúc nào; chỉ đơn giản là theo dõi số lƣợng cạnh đă đƣợc xét và dừng lại khi đã có n-1 cạnh đƣợc chấp nhận. Chúng ta giả sử rằng, các quá trình quản lý khối (heap) nhƣ thiết lập, bổ xung và lấy dữ liệu ra là đơn giản. Điều quan trọng cần chú ý ở đây là độ phức tạp của việc thiết lập một khối (heap) có m phần tử là O(m), độ phức tạp của việc tìm phần tử bé nhất là O(1) và độ phức tạp của việc khôi phục một khối (heap) sau khi bổ xung, xoá, hoặc thay đổi một giá trị là O(logm). Chính vì vậy, nếu chúng ta xét k cạnh để tìm cây bắc cầu, độ phức tạp trong việc duy trì một khối (heap) bằng O(m+klogm), độ phức tạp này bé hơn O(mlogm) nếu k có bậc bé hơn bậc của m. k tối thiểu bằng O(n) nên nếu graph là khá mỏng thì việc sử dụng khối (heap) sẽ không có lợi. Nếu graph là dày đặc thì việc lƣu trữ đó có thể đƣợc xem xét. Đây là phiên bản cuối cùng của thuật toán Kruskal, thuật toán này tận dụng các hiệu ứng nói trên. list <- Kruskal_l( n, m, lengths ) dcl length[m], ends[m,2], next[n], solution[list], l_heap[heap] for each ( node , n ) next[node]<-node l_heap <-HeapSet(m, lengths) #_accept <-0 solution <-  while ( (#_accept < n-1) and !(HeapEmpty(l_heap)) edge <- HeapPop(*l_heap) c1=FindComponent(ends[edge,1], *next) c2=FindComponent(ends[edge,2], *next) KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -37- if (c1 !=c2 ) next[c2] <- c1 solution <- Append ( edge , solution ) #_accept=#_accept+1 return( solution ) HeapSet tạo ra một khối (heap) dựa vào các giá trị cho trƣớc và trả về chính khối (heap) đó. HeapPop trả về chỉ số của giá trị ở đỉnh của khối (heap) chứ không phải bản thân giá trị đó. Điều này có lợi hơn việc trả về một giá trị vì từ chỉ số luôn biết đƣợc giá trị có chỉ số đó chứ từ giá trị không thể biết đƣợc chỉ số của giá trị đó. Cũng cần chú ý rằng HeapPop làm khối (heap) thay đổi. HeapEmpty trả về giá trị TRUE nếu khối (heap) rỗng. Mảng ends chứa các điểm cuối của các cạnh. b. Thuật toán Prim Thuật toán này có những ƣu điểm riêng biệt, đặc 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 (MST). 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 MST này; và một số các 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. Tóm lại, các thuật toán này phù hợp với các quá 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 Prim có thể đƣợc miêu tả nhƣ sau: Bắt đầu với một nút thuộc cây còn tất cả các nút khác không thuộc cây (ở ngoài cây). Trong khi còn có các nút không thuộc cây Tìm nút không thuộc cây gần nhất so với cây Đƣa nút đó vào cây và ghi lại cạnh nối nút đó với cây Thuật toán Prim dựa trên những định lý sau đây: Định lý 2.4. Một cây là một MST nếu và chỉ nếu cây đó chứa cạnh ngắn nhất trong mọi cutset chia các nút thành hai thành phần. Để thực hiện thuật toán Prim, cần phải theo dõi khoảng cách từ mỗi nút không thuộc cây tới cây và cập nhật khoảng cách đó mỗi khi có một nút đƣợc thêm vào cây. Việc đó đƣợc thực hiện dễ dàng; đơn giản chỉ là duy trì một dãy d_tree có các thông tin về khoảng cách đã nói ở trên. Quá trình đó tuân theo: KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -38- array[n] <- Prim( n , root , dist ) dcl dist[n,n] , pred[n], d_tree[n], in_tree[n] index <- FindMin() d_min <- INFINITY for each( i , n ) if(!(in_tree[j]) and (d_tree[i]< d_min)) i_min <- i d_min <- d_tree[i] return ( i_min ) void <-Scan(i) for each ( j , n ) if(!(in_tree[j]) and (d_tree[j]>dist{i,j])) d_tree[j]<- dist[i,j] pred[j]<-i d_tree <- INFINITY pred <- -1 in_tree <- FALSE d_tree(root)<-0 #_in_tree <-0 while (#_in_tree < n) i <- FindMin() in_tree[i]<- TRUE Scan(i) #_in_tree =#_in_tree + 1 return (pred) FindMin trả về một nút không thuộc cây và gần cây nhất. Scan cập nhật khoảng cách tới cây đối với các nút không thuộc cây. Có thể thấy rằng độ phức tạp của thuật toán này là O(n2); cả hai hàm FindMin và Scan có độ phức tạp là O(n) và mỗi hàm đƣợc thực hiện n lần. So sánh với thuật toán Kruskal ta thấy rằng độ phức tạp của thuật toán Prim tăng nhanh hơn so với độ phức tạp của thuật toán Kruskal nếu KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -39- m, số lƣợng các cạnh, bằng O(n2),còn nếu m có cùng bậc với n thì độ phức tạp của thuật toán Kruskal tăng nhanh hơn. Có thể tăng tốc thuật toán Prim trong trƣờng hợp graph là một graph mỏng bằng cách chỉ quan tâm đến các nút láng giềng của nút i vừa đƣợc thêm vào cây. Nếu sẵn có các thông tin kề liền, vòng lặp for trong Scan có thể trở thành. for each (j , n_adj_list[i] ) Độ phức tạp của Scan trở thành O(d) với d là bậc của nút i. Chính vì thế độ phức tạp tổng cộng của Scan giảm từ O(n2) xuống O(m). Thiết lập một tập kề liền cho toàn bộ một graph là một phép toán có độ phức tạp bằng O(m): index[nn,list] <- SetAdj(n ,m, ends) dcl ends[m,2], n_adj_list[n,list] for node = 1 to n n_adj_list[node] <-  for edge = 1 to m Append(edge, n_adj_list[end[edge,1]]) Append(edge, n_adj_list[end[edge,2]]) Có thể tăng tốc FindMin nếu ta thiết lập một khối (heap) chứa các giá trị trong d_tree. Vì thế, chúng ta có thể lấy ra giá trị thấp nhất và độ phức tạp tổng cộng của quá trình lấy ra là O(nlogn). Vấn đề ở chỗ là chúng ta phải điều chỉnh khối (heap) khi một giá trị trong d_tree thay đổi. Quá trình điều chỉnh đó có độ phức tạp là O(mlogn) trong trƣờng hợp xấu nhất vì có khả năng mỗi cạnh sẽ có một lần cập nhật và mỗi lần cập nhật đòi hỏi một phép toán có độ phức tạp là O(logn). Do đó, độ phức tap của toàn bộ thuật toán Prim là O(mlogn). Qua thí nghiệm có thể thấy rằng hai thuật toán Prim và Kruskal có tốc độ nhƣ nhau, nhƣng nói chung, thuật toán Prim thích hợp hơn với các mạng dày còn thuật toán Kruskal thích hợp hơn đối với các mạng mỏng. Tuy vậy, những thuật toán này chỉ là một phần của các thủ tục lớn và phức tạp hơn, đó là những thủ tục hoạt động hiệu quả với một trong những thuật toán này. KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -40- Hình 2.5. Graph có liên kết song song và self loop Bảng 2.1 Nút init. A C E B D A 0 0(-) 0(-) 0(-) 0(-) 0(-) B 100 10(A) 10(A) 10(A) 10(A) 10(A) C 100 2(A) 2(A) 2(A) 2(A) 2(A) D 100 100(-) 11(A) 11(A) 5(B) 5(B) E 100 7(A) 6(C) 6(C) 6(C) 6(C) Ví dụ 2.4: Trở lại hình 4.4, giả sử rằng các cạnh không đƣợc biểu diễn có độ dài bằng 100. Thuật toán Kruskal sẽ chọn (A, C), (B, D), (C, E), và loại (A, E) bởi vì nó tạo ra một chu trình với các cạnh đã đƣợc chọn là (A, C) và (C, E), chọn (A, B) sau đó dừng lại vì một cây bắc cầu hoàn toàn đã đƣợc tìm thấy. Thuật toán Prim bắt đầu từ nút A, nút A sẽ đƣợc thêm vào cây. Tiếp theo là các nút C, E, B và D. Bảng 4.1 tổng kết các quá trình thực hiện của thuật toán Prim, biểu diễn d_tree và pred khi thuật toán thực hiện. Cuối thuật toán, pred[B] là A, tƣơng ứng với (A, B) là một phần của cây. Tƣơng tự, pred chỉ ra (A, C), (B, D) và (C, E) là các phần của cây. Vì vậy, thuật toán Prim sẽ lựa chọn đƣợc cây giống với cây mà thuật toán Kruskal nhƣng thứ tự các liên kết đƣợc lựa chọn là khác nhau. Một đường đi trong một mạng là một chuỗi liên tiếp các liên kết bắt đầu từ một nút s nào đó và kết thúc tại một nút t nào đó. Những đƣờng đi nhƣ vậy đƣợc gọi là một đường đi s, t. Chú ý rằng thứ tự các liên kết trong đƣờng đi là có ý nghĩa. Một đƣờng đi có thể là hữu hƣớng hoặc vô hƣớng tuỳ thuộc vào việc các thành phần của nó là các liên kết hay là các cung. Ngƣời ta gọi một đƣờng đi là đƣờng đi đơn giản nếu không có nút nào xuất hiện quá hai lần trong đƣờng đi đó. Chú ý rằng một đƣờng đi đơn giản trong một graph đơn giản có thể đƣợc biểu diễn bằng chuỗi liên tiếp các nút mà đƣờng đi đó chứa vì chuỗi các nút đó biểu diễn duy nhất một chuỗi các liên kết . KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -41- Nếu s trùng với t thì đƣờng đi đó gọi là một chu trình, và nếu một nút trung gian xuất hiện không quá một lần thì chu trình đó đƣợc gọi là chu trình đơn giản. Một chu trình đơn giản trong một graph đơn giản có thể đƣợc biểu diễn bởi một chuỗi các nút liên tiếp. Ví dụ 2.5: Xét graph hữu hƣớng trong hình 4.4. Các thành phần liên thông bền đƣợc xác dịnh bởi {A B C D} {E F G} {H} {I} {J} Các cung (A, H), (D, I), (I, J) và (J, G) không là một phần một thành phần liên thông bền nào cả. Xem graph trong hình 4.3 là một graph vô hƣớng (nghĩa là xem các cung là các liên kết vô hƣớng), thì graph này có một thành phần duy nhất, vì thế nó là một graph liên thông. Cho một graph G = (V, E), H là một graph con nếu H = (V', E'), trong đó V' là tập con của V and E' là tập hợp con của E. Các tập con này có thể có hoặc không tuân theo quy định đã nêu. Hình 2.6. Graph hữu hướng Một graph không hề chứa các chu trình gọi là một cây. Một cây bắc cầu là một graph liên thông không có các chu trình. Những graph nhƣ vậy đƣợc gọi một cách đơn giản là cây. Khi graph không liên thông hoàn toàn đƣợc gọi là một rừng. Chúng ta thƣờng đề cập các cây trong các graph vô hƣớng. Trong các graph hữu hƣớng, có một cấu trúc tƣơng tự với cây gọi là cây phân nhánh. Một cây phân nhánh là một graph hữu hƣớng có các đƣờng đi từ một nút (gọi là nút gốc của cây phân nhánh) tới tất cả các nút khác hoặc nói một cách khác là graph hữu hƣớng có các đƣờng đi từ tất cả các nút khác đến nút gốc. Một cây phân nhánh sẽ trở thành một cây nếu nó là vô hƣớng. Các cây bắc cầu có rất nhiều thuộc tính đáng quan tâm, những thuộc tính đó khiến cho các cây bắc cầu rất hữu ích trong quá trình thiết kế mạng truyền thông. Thứ nhất, các cây bắc cầu là liên thông tối thiểu có nghĩa là: chúng là các graph liên thông nhƣng không tồn tại một tập con KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -42- các cạnh nào trong cây tạo ra một graph liên thông. Chính vì vậy, nếu mục đích chỉ đơn giản là thiết kế một mạng liên thông có giá tối thiểu thì giải pháp tối ƣu nhất là chọn một cây. Điều này có thể hiểu đƣợc vì trong một cây luôn có một và chỉ một đƣờng đi giữa một cặp nút. Điều đó không gây khó khăn đáng kể trong việc định tuyến trong cây và làm đơn giản các thiết bị truyền thông liên quan đi rất nhiều. Chú ý rằng một graph có N nút thì bất kỳ một cây nào bắc cầu tất cả các nút thì có đúng (N-1) cạnh. Bất kỳ một rừng nào có k thành phần thì chứa đúng (N-k) cạnh. Nhận xét này có thể suy ra từ lập luận sau: khi có một graph có N nút và không có cạnh nào thì có N thành phần, và cứ mỗi cạnh thêm vào nhằm kết nối hai thành phần thì số lƣợng thành phần giảm đi một. Một tập hợp các cạnh mà sự biến mất của nó chia cắt một graph (hay nói một cách khác là làm tăng số lƣợng thành phần của graph) đƣợc gọi là một tập chia cắt. Một tập chia cắt nào đó chia cắt các nút thành hai tập X và Y đƣợc gọi là một cutset hoặc một XY-cutset. Hầu hết các vấn đề cần quan tâm đều liên quan đến các cutset tối thiểu (nghiă là các cutset không phải là tập con của một cutset khác). Trong một cây, một cạnh bất kỳ là một cutset tối thiểu. Một tập tối thiểu các nút mà sự biến mất của nó phân chia các nút còn lại thành hai tập gọi là một cut. Các vấn đề cần quan tâm cũng thƣờng liên quan đến các cut tối thiểu. Ví dụ 2.6: Hình 2.6 biểu diễn một graph vô hƣớng. Các tập các liên kết {(A, C), (B, D)} và {(C, E), (D, E), (E, F)} là các ví dụ của các cutset tối thiểu. Tập cuối cùng là một ví dụ về một loại tập trong đó tập các liên kết đi tới một nút thành viên bất kỳ đều là một cutset và các cutset đó chia cắt nút đó ra khỏi các nút khác. Tập (C, D) là một cut. Nút A cũng là một cut. Một nút duy nhất mà sự biến mất của nó chia cắt graph gọi là một điểm khớp nối. Tập hợp các liên kết: {(A, B), (A, C), (A, G), (C, D), (C, E), (E, F)} là một cây. Bất kỳ tập con nào của tập này, kể cả tập đầy hay tập rỗng, đều là một rừng. KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -43- Hình 2.7. Các cutset, các cut, các cây b. Các mô hình định tuyến thông dụng Định tuyến ngắn nhất (Shortest path Routing) 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. 1. Thuật toán Dijkstra Tất cả các thuật toán tìm đƣờng đi ngắn nhất đều dựa vào các nhận xét đƣợc minh hoạ trên hình 4.5, đó là việc lồng nhau giữa các đƣờng đi ngắn nhất nghĩa là một nút k thuộc một đƣờng đi ngắn nhất từ i tới j thì đƣờng đi ngắn nhất từ i tới j sẽ bằng đƣờng đi ngắn nhất từ i KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -44- tới k kết hợp với đƣờng đi ngắn nhất từ j tới k. Vì thế, chúng ta có thể tìm đƣờng đi ngắn nhất bằng công thức đệ quy sau: )(min kjik k ij ddd  dxy là độ dài của đƣờng đi ngắn nhất từ x tới y. Khó khăn của cách tiếp cận này là phải có một cách khởi động đệ quy nào đó vì chúng ta không thể khởi động với các giá trị bất kỳ ở vế phải của phƣơng trình 4.2. Có một số cách để thực hiện việc này, mỗi cách là cơ sở cho một thuật toán khác nhau. Hình 2.8. Các đường ngắn nhất lồng nhau Thuật toán Dijkstra phù hợp cho việc tìm đƣờng đi ngắn nhất từ một nút i tới tất cả các nút khác. Bắt đầu bằng cách thiết lập dii = 0 và dij =   i  j sau đó thiết lập dij  lij  j là nút kề cận của i Sau đó tìm nút j có dij là bé nhất. Tiếp đó lấy chính nút j vừa chọn để khai triển các khoảng cách các nút khác, nghĩa là bằng cách thiết lập dikmin (dik, dij+ljk) Tại mỗi giai đoạn của quá trình, giá trị của dik là giá trị ƣớc lƣợng hiện có của đƣờng đi ngắn nhất từ i tới k; và thực ra là độ dài đƣờng đi ngắn nhất đã đƣợc tìm cho tới thời điểm đó. Xem djk nhƣ là nhãn trên nút k. Quá trình sử dụng một nút để triển khai các nhãn cho các nút khác gọi là quá trình quét nút. Thực hiện tƣơng tự, tiếp tục tìm các nút chƣa đƣợc quét có nhãn bé nhất và quét nó. Chú ý rằng, vì giả thiết rằng tất cả các ljk đều dƣơng do đó một nút không thể gán cho nút khác một nhãn bé hơn chính nhãn của nút đó. Vì vậy, khi một nút đƣợc quét thì việc quét lại nó nhất thiết không bao giờ xảy ra. Vì thế, mỗi nút chỉ cần đƣợc quét một lần. Nếu nhãn trên một nút thay đổi, nút đó phải đƣợc quét lại. Thuật toán Dijkstra có thể đƣợc viết nhƣ sau: array[n] <-Dijkstra (n, root, dist) dcl dist[n,n], pred[n], sp_dist[n], scanned[n] index <- FindMin( ) d_min <- INFINITY KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -45- for each (i , n ) if (!(scanned[j])&& (sp_dist[i]< d_min) ) i_min <- i d_min <- sp_dist[i] return (i_min) void <- Scan( i ) for each ( j , n) if((sp_dist[j] > sp_dist[i] + dist[i,j])) sp_dist[j]<- sp_dist[i] + dist[i,j] pred[j]<- i sp_dist<- INFINITY pred <- -1 scanned <-FALSE sp_dist[root]<- 0 #_scanned <- 0 while (#_scanned < n ) i <- FindMin() Scan( i ) #_scanned= #_scanned + 1 return ( pred ) Trong thuật toán đã viết ở trên, hàm chỉ trả về dãy pred , dãy này chứa tất cả các đƣờng đi. Hàm cũng có thể trả về dãy sp_dist, dãy này chứa độ dài của các đƣờng đi, hoặc hàm trả về cả hai dãy nếu cần thiết. Thuật toán trông rất quen thuộc. Nó gần giống với thuật toán tìm cây bắc cầu tối thiểu Prim. Chỉ khác nhau ở chỗ, các nút trong thuật toán này đƣợc gắn nhãn là độ dài của toàn bộ đƣờng đi chứ không phải là độ dài của một cạnh. Chú ý rằng thuật toán này thực hiện với graph hữu hƣớng trong khi thuật toán Prim chỉ thực hiện với graph vô hƣớng. Tuy nhiên về mặt cấu trúc, các thuật toán là rất đơn giản. Độ phức tạp của thuật toán Dijkstra, cũng giống nhƣ độ phức tạp của thuật toán Prim , là O(N2). Cũng giống nhƣ thuật toán Prim, thuật toán Dijkstra thích hợp với các mạng dày và đặc biệt thích hợp với các quá trình thực hiện song song (ở đây phép toán scan có thể đƣợc thực hiện KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -46- song song, về bản chất độ phức tạp của quá trình đó là O(1) chứ không phải là O(N)). Hạn chế chủ yếu của thuật toán này là không có đƣợc nhiều ƣu điểm khi mạng là mỏng và chỉ phù hợp với các mạng có độ dài các cạnh là dƣơng. Hình 2.9. Các đường đi ngắn nhất từ A Ví dụ 2.7: Xét một mạng trong hình 4.6. Mục tiêu ở đây là tìm các đƣờng đi ngắn nhất từ nút A tới các nút khác. Khởi đầu, A đƣợc gắn nhãn 0 và các nút khác đƣợc gắn nhãn là vô cùng lớn. Quét nút A, B đƣợc gán bằng 5 và C đƣợc gán là 1. C là nút mang nhãn bé nhất nên sau đó C đƣợc quét và B đƣợc gán bằng 4 (=1+3), trong khi D đƣợc gán bằng 6. Tiếp theo B (có nhãn bằng 4) đƣợc quét; D và E đƣợc gán lần lƣợt là 5 và 10. Sau đó D (có nhãn bằng 5) đƣợc quét và F đƣợc gán bằng 9. E đƣợc quét và dẫn đến không có nhãn mới. F là nút có nhãn bé nhất nên không cần phải quét vì không có nút nào phải đánh nhãn lại. Mỗi nút chỉ đƣợc quét một lần. Chú ý rằng việc quét các nút có các nhãn theo thứ tự tăng dần là một điều cần lƣu ý vì trong quá trình thực hiện thuật toán một số nút đƣợc đánh lại số. Các nút đƣợc quét ngay tức thì hoặc là phải đƣợc quét lại sau đó. Chú ý rằng các đƣờng đi từ A đến các nút khác (nghĩa là (A, C), (C, B), (B, D), (B, E) và (D, F)) tạo ra một cây. Điều này không là một sự trùng hợp ngẫu nhiên. Nó là hệ quả trực tiếp từ việc lồng nhau của các đƣờng đi ngắn nhất. Chẳng hạn, nếu k thuộc đƣờng đi ngắn nhất từ i tới j thì đƣờng đi ngắn nhất từ i tới j sẽ là tổng của đƣờng đi ngắn nhất từ i tới k và đƣờng đi ngắn nhất từ k tới j. Tƣơng tự nhƣ trong ví dụ minh hoạ cho thuật toán Prim, kết quả của ví dụ trên có thể đƣợc trình bày một cách ngắn gọn nhƣ bảng sau: KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -47- Bảng 2.2 Nút init. A(0) C(1) B(4) D(5) F(9) E(10) A 0(-) 0(-) 0(-) 0(-) 0(-) 0(-) 0(-) B  (-) 5(A) 4(C) 4(C) 4(C) 4(C) 4(C) C  (-) 1(A) 1(A) 1(A) 1(A) 1(A) 1(A) D  (-)  (-) 6(C) 5(B) 5(B) 5(B) 5(B) E  (-)  (-)  (-) 10(B) 10(B) 10(B) 10(B) F  (-)  (-)  (-)  (-) 9(D) 9(D) 9(D) 2. Thuật toán Bellman Một thuật toán khác của dạng thuật toán Dijkstra do Bellman phát biểu và sau đó đƣợc Moore và Page phát triển, đó là việc quét các nút theo thứ tự mà chúng đƣợc đánh nhãn. Việc đó loại trừ việc phải tìm nhãn nhỏ nhất, nhƣng tạo ra khả năng; một nút có thể cần quét nhiều hơn một lần. Trong dạng đơn giản nhất, thuật toán Bellman duy trì một hàng đợi các nút để quét. Khi một nút đƣợc đánh nhãn nó đƣợc thêm vào hàng đợi trừ khi nó đã tồn tại trong hàng đợi. Hàng đợi đƣợc quản lý theo quy tắc vào trƣớc, ra trƣớc. Vì thế các nút đƣợc quét theo thứ tự mà chúng đƣợc đánh nhãn. Nếu một nút đƣợc đánh nhãn lại sau khi nút đó đƣợc quét thì nó đƣợc thêm vào sau hàng đợi và đƣợc quét lần nữa. Ví dụ 2.8: Trong ví dụ ở hình 2.9, chúng ta bắt đầu quá trình bằng các đặt nút A vào hàng đợi. Quét A các nhãn 5 và 1 lần lƣợt đƣợc gán cho nút B và C, đồng thời các nút B và C đƣợc đƣa vào hàng đợi (vì các nút này nhận giá trị mới và chƣa có mặt trong hàng đợi). Tiếp đó chúng ta quét nút B và các nút E và D đƣợc đánh nhãn lần lƣợt là 11 và 6. D và E cũng đƣợc đặt vào hàng đợi. Sau đó chúng ta quét C, khi đó B đƣợc gán nhãn là 4 và lại đƣợc đặt vào sau hàng đợi. E đƣợc quét và F đƣợc gán nhãn 13 và đƣa vào hàng đợi. D đƣợc quét và F đƣợc gán nhãn là 10; F vẫn còn ở trong hàng đợi nên F không đƣợc đƣa vào hàng đợi. B đƣợc quét lần thứ hai. trong lần quét này E và D lần lƣợt đƣợc đánh nhãn là 10 và 5 đồng thời cả hai nút đƣợc đặt vào hàng đợi. F đƣợc quét và không đánh nhãn nút nào cả. E đƣợc quét không đánh nhãn nút nào cả. D đƣợc quét và F đƣợc đánh nhãn 9 và đƣợc đƣa vào hàng đợi. F đƣợc quét và không đánh dấu nút nào cả. Các nút B, C, D và F đƣợc quét hai lần. Đó là cái giá phải trả cho việc không quét các nút theo thứ tự. Mặt khác trong thuật toán này không cần thiết phải tìm kiếm các nút có nhãn nhỏ nhất. Cũng nhƣ trong hai ví dụ 4.4 và 4.5 cho thuật toán Prim và thuật toán Dijkstra, chúng ta có thể trình bày kết quả của các quá trình trong ví dụ này nhƣ trong bảng sau KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -48- Bảng 2.3 Nút init. A(0) B(5) C(1) E(11) D(6) A 0(-) A 0(-) B 0(-) C 0(-) E 0(-) D 0(-) B B  (-) 5(A) C 5(A) E 4(C) D 4(C) B 4(C) F C  (-) 1(A) 1(A) D 1(A) B 1(A) F 1(A) D  (-)  (-) 6(B) 6(B) 6(B) 6(B) E  (-)  (-) 11(B) 11(B) 11(B) 11(B) F  (-)  (-)  (-)  (-) 13(E) 10(D) B(4) F(10) E(10) D(5) F(9) A 0(-) F 0(-) E 0(-) D 0(-) F 0(-) B 4(C) E 4(C) D 4(C) 4(C) 4(C) C 1(A) D 1(A) 1(A) 1(A) 1(A) D 5(B) 5(B) 5(B) 5(B) 5(B) E 10(B) 10(B) 10(B) 10(B) 10(B) F 10(D) 10(D) 10(D) 9(D) 9(D) Thuật toán có thể viết nhƣ sau: array[n]<-Bellman (n, root, dist) dcl dist[n][n], pred[n], sp_dist[n], in_queue[n] scan_queue[queue] void <- Scan( i ) in_queue[i]<- FALSE for j=1 to n if((sp_dist[j] > sp_diat[i] + dist[i,j])) sp_dist[j]<- sp_diat[i] + dist[i,j] pred[j]<- i if ( not ( in_queue[j] ) ) Push(scan_queue, j ) in_queue[j]<- TRUE sp_dist<- INFINITY pred <- -1 in_queue <-FALSE initialize_queue( scan_queue ) sp_dist[root]<- 0 KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -49- Push(scan_queue , root ) in_queue <-TRUE while (not(Empty( scan_queue )) i <- Pop(scan_queue) Scan( i ) return ( pred ) Một hàng đợi chuẩn đƣợc sử dụng quá trình trên. Có thể sử dụng dãy in_queue để theo dõi nút nào đang hiện có trong hàng đợi. Theo quá trình đƣợc viết ở trên thì thuật toán Bellman là một quá trình tìm kiếm theo chiều rộng. Ngƣời ta đã chứng minh đƣợc rằng trong trƣờng hợp xấu nhất, một nút đƣợc quét n-1 lần. Vì vậy quá trình quét trong trƣờng hợp xấu nhất có độ phức tạp là O(n) với n là số lƣợng các nút. Từ đó suy ra rằng độ phức tạp của toàn bộ thuật toán là O(n3). Tuy nhiên trong thực tế các nút không thƣờng xuyên đƣợc quét lại nhiều lần. Trong hầu hết các trƣờng hợp thực tế, số lần quét trung bình trên một nút là rất nhỏ, tối đa là 3 hoặc 4, ngay cả khi mạng có hàng ngàn nút. Nếu bậc trung bình của nút nhỏ, điều này thƣờng xảy ra trong các mạng thực tế, thì thời gian cho việc tìm kiếm nút chƣa quét bé nhất là phần có ảnh hƣởng nhất của thuật toán Dijkstra. Vì vậy trong thực tế thuật toán Bellman đƣợc xem là nhanh hơn so với thuật toán Dijkstra mặc dù độ phức tạp trong trƣờng hợp xấu nhất của thuật toán Bellman lớn hơn. Tƣơng tự có thể cải tiến độ phức tạp của thủ tục Scan bằng cách duy trì một danh sách kề cận cho mỗi nút. Độ phức tạp của Scan trở thành O(d) thay vì O(n) với d là bậc của nút đang quét. Vì vậy, trên thực tế độ phức tạp của thuật toán Bellman thƣờng bằng O(E) với E là số cạnh của graph. Ngoài việc có thể cải thiện chất lƣợng trung bình của thuật toán trong nhiều trƣờng hợp, thuật toán Bellman còn có một ƣu điểm nữa đó là thuật toán hoạt động ngay cả khi độ dài các cạnh là các giá trị âm. Thuật toán Dijkstra dựa vào quy tắc: một nút không thể gán cho nút khác một nhãn bé hơn nhãn của chính nút. Điều đó chỉ đúng khi không có các cung có độ dài là âm trong khi thuật toán Bellman không cần phải giả thiết nhƣ vậy và quét lại các nút mỗi khi nút đó đƣợc gán nhãn lại. Vì thế, thuật toán này rất phù hợp khi xuất hiện các cung có độ dài âm. Tuy nhiên cần chú ý rằng khi graph có một chu trình có tổng độ dài âm thì thậm chí thuật toán Bellman cũng không khả dụng. Trong trƣờng hợp này, thuật toán không kết thúc và các nút tiếp tục đánh nhãn các nút khác một cách vô hạn. Có một số dạng khác nhau của thuật toán KHOA ĐIỆN-ĐIỆN TỬ ĐHSP KT HƯNG YÊN TS. NGUYỄN VĂN VINH MẠNG THÔNG TIN -50- Bellman, ngoài thuật toán này ra còn có một số các thuật toán tìm đƣờng đi ngắn nhất từ một điểm tới các điểm khác trong trƣờng hợp khác nhau. 3. Thuật toán Floyd Có thể thấy rằng bài toán tìm kiếm đƣờng ngắn nhất giữa mọi cặp nút nặng nề gấp N lần bài toán tìm đƣờng đi ngắn nhất từ một nút đến tất cả các nút khác. Một khả năng có thể đó là sử dụng thuật toán Bellman hoặc thuật toán Dijkstra N lần, bắt đầu từ mỗi nút nguồn. Một khả năng khác, đặc biệt thích hợp với các mạng dày, là sử dụng thuật toán Floyd. Thuật toán Floyd dựa vào quan hệ đệ quy đã đƣợc trình bày trong phần giới thiệu thuật toán Dijkstra, nhƣng thuật toán này sử dụng quan hệ đệ quy đó theo một cách khác. Lúc này, dij(k) đƣợc định nghĩa là đƣờng đi ngắn nhất từ i tới j sử dụng các nút đƣợc đánh số là k hoặc thấp hơn nhƣ là các nút trung gian. Vì thế dij(0) đƣợc định nghiã nhƣ là lij, độ dài của liên kết từ nút i tới nút j, nếu liên kết đó tồn tại hoặc dij(0) sẽ bằng vô cùng nếu liên kết đó không tồn tại. Vì vậy, dij(k) = min (dij(k-1), dik(k-1) + dkj(k-1) ) nghĩa là, chúng ta chỉ quan tâm đến việc sử dụng nút k nhƣ là một điểm quá giang cho mỗi đƣờng đi từ i tới j. Thuật toán có thể đƣợc viết nhƣ sau: array[n] <-Floyd (n, dist) dcl dist[n][n], pred[n][n], sp_dist[n,n] for each (i , n ) for each (i , n ) sp_dist[i,j] <- dist[i, j] pred[i, j]<- i for each (k , n ) for each (i , n ) for each (j , n ) if((sp_dist[i,j]> sp_dist[i,k] + dist[k,j])) sp_dist[i,j]<- sp_dist[i,k] + dist[k,j] pred[i, j]<- pred[k,j] return ( pred ) pred[i,j] chứa nút