Đồ án Quản trị mạng máy tính

TRƯỜNG ĐẠI HỌC TÔN ĐỨC THẮNG KHOA ĐIỆN – ĐIỆN TỬ BỘ MÔN ĐIỆN TỬ VIỄN THÔNG ĐỒ ÁN III QUẢN TRỊ MẠNG MÁY TÍNH SVTH : DMZ BMW TP.Hồ Chí Minh, ngày 30 tháng 11 năm 2008 Phần 1: Tổng quan về mạng máy tính Định nghĩa Mạng Máy Tính: Mạng máy tính là một nhóm các máy tính, thiết bị ngoại vi được kết nối với nhau thông qua các phương tiện truyền dẫn như cáp, sóng điện từ, tia hồng ngoại…giúp cho các thiết bị này có thể trao đổi dữ liệu với nhau một cách dễ dàng. Tại sao cần có mạng? Ngày nay với một lượng lớn về thông tin, nhu cầu xử lý thông tin ngày càng cao. Mạng máy tính hiện nay trở nên quá quen thuộc đối với chúng ta, trong mọi lĩnh vực như khoa học, quân sự, quốc phòng, thương mại, dịch vụ, giáo dục... Hiện nay ở nhiều nơi mạng đã trở thành một nhu cầu không thể thiếu được. Người ta thấy được việc kết nối các máy tính thành mạng cho chúng ta những khả năng mới to lớn như: Sử dụng chung tài nguyên: Những tài nguyên của mạng (như thiết bị, chương trình, dữ liệu) khi được trở thành các tài nguyên chung thì mọi thành viên của mạng đều có thể tiếp cận được mà không quan tâm tới những tài nguyên đó ở đâu. Tăng độ tin cậy của hệ thống: Người ta có thể dễ dàng bảo trì máy móc và lưu trữ (backup) các dữ liệu chung và khi có trục trặc trong hệ thống thì chúng có thể được khôi phục nhanh chóng. Trong trường hợp có trục trặc trên một trạm làm việc thì người ta cũng có thể sử dụng những trạm khác thay thế. Nâng cao chất lượng và hiệu quả khai thác thông tin: Khi thông tin có thể được dùng chung thì nó mang lại cho người sử dụng khả năng tổ chức lại các công việc với những thay đổi về chất như: Đáp ứng những nhu cầu của hệ thống ứng dụng kinh doanh hiện đại. Cung cấp sự thống nhất giữa các dữ liệu. Tăng cường năng lực xử lý nhờ kết hợp các bộ phận phân tán. Tăng cường truy nhập tới các dịch vụ mạng khác nhau đang được cung cấp trên thế giới. Phân loại mạng máy tính: Mạng cục bộ LAN (Local Area Network): Mạng LAN là một nhóm các máy tính và các thiết bị truyền thông mạng được nối kết với nhau trong một khu vực nhỏ như một toà nhà cao ốc, khuôn viên trường đại học, khu giải trí… Các mạng LAN thường có các đặc điểm sau đây: Băng thông lớn có khả năng chạy các ứng dụng trực tuyến như xem phim, hội thảo qua mạng. Kích thước mạng bị giới hạn bởi các thiết bị. Chi phí các thiết bị mạng LAN tương đối rẻ. Quản trị đơn giản. Hình 1.1 Mạng đô thị MAN (Metropolitan Area Network): Mạng MAN gần giống như mạng LAN nhưng giới hạn của nó là một thành phố hay một quốc gia. Mạng MAN nối kết các mạng LAN lại với nhau thông qua các phương tiện truyền dẫn khác nhau (cáp quang, cáp đồng, sóng…) và các phương thức truyền thông khác nhau. Đặc điểm của mạng MAN : Băng thông mức trung bình, đủ để phục vụ các ứng dụng cấp thành phố hay quốc gia như chính phủ điện tử, thương mại điện tử, các ứng dụng của các ngân hàng… Do MAN nối kết nhiều LAN với nhau nên độ phức tạp cũng tăng đồng thời việc quản lý sẽ khó khăn hơn. Chi phí các thiết bị mạng MAN tương đối đắt tiền. Mạng diện rộng WAN (Wide Area Network): Mạng WAN bao phủ vùng địa lý rộng lớn có thể là một quốc gia, một lục địa hay toàn cầu. Mạng WAN thường là mạng của các công ty đa quốc gia hay toàn cầu điển hình là mạng Internet. Do phạm vi rộng lớn của mạng WAN nên thông thường mạng WAN là tập hợp các mạng LAN, MAN nối lại với nhau bằng các phương tiện như: vệ tinh (satellites), sóng viba (microwave), cáp quang, cáp điện thoại. Đặc điểm của mạng WAN: Băng thông thấp, dễ mất kết nối thường chỉ phù hợp với các ứng dụng online như e-mail, web, ftp… Phạm vi hoạt động rộng lớn không giới hạn. Do kết nối của nhiều LAN, MAN lại với nhau nên mạng rất phức tạp và có tính toàn cầu nên thường là các tổ chức quốc tế đứng ra qui định và quản lý. Chi phí cho các thiết bị và các công nghệ mạng WAN rất đắt tiền. Hình 1.2 Mạng Internet: Mạng Internet là trường hợp đặc biệt của mạng WAN, nó chứa các dịch vụ toàn cầu như Mail, Web, Chat, FTP và phục vụ miễn phí cho mọi người. Sự phân biệt giữa mạng cục bộ và mạng diện rộng: Mạng cục bộ và mạng diện rộng có thể được phân biệt bởi: địa phương hoạt động, tốc độ đường truyền và tỷ lệ lỗi trên đường truyền, chủ quản của mạng, đường đi của thông tin trên mạng, dạng chuyển giao thông tin. Địa phương hoạt động: Liên quan đến khu vực địa lý thì mạng cục bộ sẽ là mạng liên kết các máy tính nằm ở trong một khu vực nhỏ. Khu vực có thể bao gồm một tòa nhà hay là một khu nhà... Điều đó hạn chế bởi khoảng cách đường dây cáp được dùng để liên kết các máy tính của mạng cục bộ (hạn chế đó còn là hạn chế của khả năng kỹ thuật của đường truyền dữ liệu). Ngược lại mạng diện rộng là mạng có khả năng liên kết các máy tính trong một vùng rộng lớn như là một thành phố, một miền, một đất nước, mạng diện rộng được xây dựng để nối hai hoặc nhiều khu vực địa lý riêng biệt. Tốc độ đường truyền và tỷ lệ lỗi trên đường truyền: Do các đường cáp của mạng cục bộ được xây dựng trong một khu vực nhỏ cho nên nó ít bị ảnh hưởng bởi tác động của thiên nhiên (như là sấm chớp, ánh sáng...). Điều đó cho phép mạng cục bộ có thể truyền dữ liệu với tốc độ cao mà chỉ chịu một tỷ lệ lỗi nhỏ. Ngược lại với mạng diện rộng do phải truyền ở những khoảng cách khá xa với những đường truyền dẫn dài có khi lên tới hàng ngàn km. Do vậy mạng diện rộng không thể truyền với tốc độ quá cao vì khi đó tỷ lệ lỗi sẽ trở nên khó chấp nhận được. Mạng cục bộ thường có tốc độ truyền dữ liệu từ 4 đến 16 Mbps và đạt tới 100 Mbps nếu dùng cáp quang. Còn phần lớn các mạng diện rộng cung cấp đường truyền có tốc độ thấp hơn nhiều như T1 với 1.544 Mbps hay E1 với 2.048 Mbps. (Ở đây bps (Bit Per Second) là một đơn vị trong truyền thông tương đương với 1 bit được truyền trong một giây, ví dụ như tốc độ đường truyền là 1 Mbps tức là có thể truyền tối đa 1 Megabit trong 1 giây trên đường truyền đó). Thông thường trong mạng cục bộ tỷ lệ lỗi trong truyền dữ liệu vào khoảng 1/107- 108 còn trong mạng diện rộng thì tỷ lệ đó vào khoảng 1/106 - 107 Chủ quản và điều hành của mạng: Do sự phức tạp trong việc xây dựng, quản lý, duy trì các đường truyền dẫn nên khi xây dựng mạng diện rộng người ta thường sử dụng các đường truyền được thuê từ các công ty viễn thông hay các nhà cung cấp dịch vụ truyền số liệu. Tùy theo cấu trúc của mạng những đường truyền đó thuộc cơ quan quản lý khác nhau như các nhà cung cấp đường truyền nội hạt, liên tỉnh, liên quốc gia. Các đường truyền đó phải tuân thủ các quy định của chính phủ các khu vực có đường dây đi qua như: tốc độ, việc mã hóa. Còn đối với mạng cục bộ thì công việc đơn giản hơn nhiều, khi một cơ quan cài đặt mạng cục bộ thì toàn bộ mạng sẽ thuộc quyền quản lý của cơ quan đó. Đường đi của thông tin trên mạng: Trong mạng cục bộ thông tin được đi theo con đường xác định bởi cấu trúc của mạng. Khi người ta xác định cấu trúc của mạng thì thông tin sẽ luôn luôn đi theo cấu trúc đã xác định đó. Còn với mạng diện rộng dữ liệu cấu trúc có thể phức tạp hơn nhiều do việc sử dụng các dịch vụ truyền dữ liệu. Trong quá trình hoạt động các điểm nút có thể thay đổi đường đi của các thông tin khi phát hiện ra có trục trặc trên đường truyền hay khi phát hiện có quá nhiều thong tin cần truyền giữa hai điểm nút nào đó. Trên mạng diện rộng thông tin có thể có các con đường đi khác nhau, điều đó cho phép có thể sử dụng tối đa các năng lực của đường truyền hay nâng cao điều kiện an toàn trong truyền dữ liệu. Dạng chuyển giao thông tin: Phần lớn các mạng diện rộng hiện nay được phát triển cho việc truyền đồng thời trên đường truyền nhiều dạng thông tin khác nhau như: video, tiếng nói, dữ liệu... Trong khi đó các mạng cục bộ chủ yếu phát triển trong việc truyền dữ liệu thông thường. Điều này có thể giải thích do việc truyền các dạng thông tin như video, tiếng nói trong một khu vực nhỏ ít được quan tâm hơn như khi truyền qua những khoảng cách lớn. Các hệ thống mạng hiện nay ngày càng phức tạp về chất lượng, đa dạng về chủng loại và phát triển rất nhanh về chất. Trong sự phát triển đó số lượng những nhà sản xuất từ phần mềm, phần cứng máy tính, các sản phẩm viễn thông cũng tăng nhanh với nhiều sản phẩm đa dạng. Chính vì vậy vai trò chuẩn hóa cũng mang những ý nghĩa quan trọng. Tại các nước các cơ quan chuẩn quốc gia đã đưa ra các những chuẩn về phần cứng và các quy định về giao tiếp nhằm giúp cho các nhà sản xuất có thể làm ra các sản phẩm có thể kết nối với các sản phẩm do hãng khác sản xuất. Các mô hình xử lý mạng: Cơ bản có 3 loại mô hình xử lý mạng bao gồm: Mô hình xử lý mạng tập trung. Mô hình xử lý mạng phân phối. Mô hình xử lý mạng cộng tác. Mô hình xử lý mạng trung tâm: Toàn bộ các tiến trình xử lý diễn ra tại máy tính trung tâm. Các máy trạm cuối (Terminals) được nối mạng với máy tính trung tâm và chỉ hoạt động như những thiết bị nhập xuất dữ liệu cho phép người dùng xem trên màn hình và nhập liệu bàn phím. Các máy trạm đầu cuối không lưu trữ và xử lý dữ liệu . Mô hình xử lý mạng trên có thể triển khai trên hệ thống phần cứng hoặc phần mềm được cài đặt trên Server. Ưu điểm: dữ liệu được bảo mật an toàn, dễ backup và diệt virus. Chi phí các thiết bị thấp. Khuyết điểm: khó đáp ứng được các yêu cầu của nhiều ứng dụng khác nhau, tốc độ truy xuất chậm. Hình 1.3 Mô hình xử lý mạng phân phối: Các máy tính có khả năng hoạt động độc lập, các công việc được tách nhỏ và giao cho nhiều máy tính khác nhau thay vì tập trung xử lý trên máy trung tâm. Tuy dữ liệu được xử lý và lưu trữ tại máy cục bộ nhưng các máy tính này được nối mạng với nhau nên chúng có thể trao đổi dữ liệu và dịch vụ. Ưu điểm: truy xuất nhanh, phần lớn không giới hạn các ứng dụng. Khuyết điểm: dữ liệu lưu trữ rời rạc khó đồng bộ, backup và rất dễ nhiễm virus. Hình 1.4 Mô hình xử ký mạng công tác: Mô hình xử lý mạng cộng tác bao gồm nhiều máy tính có thể hợp tác để thực hiện một công việc. Một máy tính có thể mượn năng lực xử lý bằng cách chạy các chương trình trên các máy nằm trong mạng. Ưu điểm: rất nhanh và mạnh, có thể dùng để chạy các ứng dụng có các phép toán lớn Khuyết điểm: các dữ liệu được lưu trữ trên các vị trí khác nhau nên rất khó đồng bộ và backup, khả năng nhiễm virus rất cao. Các mô hình quản lý mạng: Workgroup: Trong mô hình này các máy tính có quyền hạng ngang nhau và không có các máy tính chuyên dụng làm nghiệp vụ cung cấp dịch vụ hay quản lý. Các máy tính tự bảo mật và quản lý tài nguyên của riêng mình. Đồng thời các máy tính cục bộ này cũng tự chứng thực cho người dùng cục bộ. Domain: Ngược lại với mô hình Workgroup, mô hình Domain thì việc quản lý và chứng thực người dùng mạng tập trung tại máy tính Primary Domain Controller. Các tài nguyên mạng cũng được quản lý tập trung và cấp quyền hạn cho từng người dùng. Lúc đó trong hệ thống có các máy tính chuyên dụng làm nhiệm vụ cung cấp các dịch vụ và quản lý các máy trạm. Các mô hình ứng dụng mạng: Mạng ngang hang (Peer to Peer): Mạng ngang hàng cung cấp việc kết nối cơ bản giữa các máy tính nhưng không có bất kỳ một máy tính nào đóng vai trò phục vụ. Một máy tính trên mạng có thể vừa là Client vừa là Server. Trong môi trường này người dùng trên từng máy tính chịu trách nhiệm điều hành và chia sẻ tài nguyên của máy tính mình. Mô hình này chỉ phù hợp với tổ chức nhỏ, số người giới hạn (thông thường nhỏ hơn 10 người) và không quan tâm đến vấn đề bảo mật. Mạng ngang hàng thường dùng các hệ điều hành sau: Win95, Windows for Workgroup, WinNT Workstation, Win2000 Proffessional, OS/2… Ưu điểm: Do mô hình mạng ngang hàng đơn giản nên dễ cài đặt, tổ chức và quản trị, chi phí thiết bị cho mô hình này thấp. Khuyết điểm: Không cho phép quản lý tập trung nên dữ liệu phân tán, khả năng bảo mật thấp rất dễ bị xâm nhập. Các tài nguyên không được sắp xếp nên rất khó định vị và tìm kiếm. Hình 1.5 Mạng khách chủ (Client-Server) Trong mô hình mạng khách chủ có một hệ thống máy tính cung cấp các tài nguyên và dịch vụ cho cả hệ thống mạng sử dụng gọi là các máy chủ (Server). Một hệ thống máy tính sử dụng các tài nguyên và dịch vụ này được gọi là máy khách (Client). Các Server thường có cấu hình mạnh (tốc độ xử lý nhanh, kích thước lưu trữ lớn) hoặc là các máy chuyên dụng. Hệ điều hành mạng dùng trong mô hình Client - Server là WinNT, Novell Netware, Unix,Win2K… Ưu điểm: Do các dữ liệu được lưu trữ tập trung nên dễ bảo mật, backup và đồng bộ với nhau. Tài nguyên và dịch vụ được tập trung nên dễ chia sẻ và quản lý và có thể phục vụ cho nhiều người dùng. Khuyết điểm: Các Server chuyên dụng rất đắt tiền, phải có nhà quản trị cho hệ thống. Hình 1.6 Kiến trúc mạng cục bộ: Hình trang mạng (Network Topology): Topology mạng: Cách kết nối các máy tính với nhau về mặt hình học mà ta gọi là tô pô của mạng. Có 2 kiểu nối mạng chủ yếu đó là: Nối kiểu điểm – điểm (point – to – point) Nối kiểu điểm – nhiều điểm (point – to – multipoint hay broadcast) Point to Point: Các đường truyền nối từng cặp nút với nhau và mỗi nút đều có trách nhiệm lưu trữ tạm thời sao đó chuyển tiếp dữ liệu đi cho tới đích. Do cách làm việc như vậy nên mạng kiểu này còn được gọi là mạng “lưu và chuyển tiếp“ (store and forward). Point to multipoint: Tất cả các nút phân chia nhau một đường truyền vật lý chung. Dữ liệu gửi đi từ một nút nào đó sẽ được tiếp nhận bởi tất cả các nút còn lại trên mạng, bởi vậy chỉ cần chỉ ra địa chỉ đích của dữ liệu để căn cứ vào đó các nút tra xem dữ liệu đó có phải gửi cho mình không. Mạng hình sao (Star): Mạng hình sao có tất cả các trạm được kết nối với một thiết bị trung tâm có nhiệm vụ nhận tín hiệu từ các trạm và chuyển đến trạm đích. Tuỳ theo yêu cầu truyền thông trên mạng mà thiết bị trung tâm có thể là Switch, router, hub hay máy chủ trung tâm. Vai trò của thiết bị trung tâm là thiết lập các liên kết Point to Point. Ưu điểm: Thiết lập mạng đơn giản, dễ dàng cấu hình lại mạng (thêm, bớt các trạm), dễ dàng kiểm soát và khắc phục sự cố, tận dụng được tối đa tốc độ truyền của đường truyền vật lý. Khuyết điểm: Độ dài đường truyền nối một trạm với thiết bị trung tâm bị hạn chế (trong vòng 100m, với công nghệ hiện nay). Hình 1.7 Mạng trục tuyến tính (Bus): Tất cả các trạm phân chia một đường truyền chung (bus). Đường truyền chính được giới hạn hai đầu bằng hai đầu nối đặc biệt gọi là terminator. Mỗi trạm được nối với trục chính qua một đầu nối chữ T (T-connector) hoặc một thiết bị thu phát (transceiver). Mô hình mạng Bus hoạt động theo các liên kết Point to Multipoint hay Broadcast. Ưu điểm: Dễ thiết kế, chi phí thấp. Khuyết điểm: Tính ổn định kém, chỉ một nút mạng hỏng là toàn bộ mạng bị ngừng hoạt động. Hình 1.8 Mạng hình vòng (Ring): Trên mạng hình vòng tín hiệu được truyền đi trên vòng theo một chiều duy nhất. Mỗi trạm của mạng được nối với nhau qua một bộ chuyển tiếp (repeater) có nhiệm vụ nhận tín hiệu rồi chuyển tiếp đến trạm kế tiếp trên vòng. Như vậy tín hiệu được lưu chuyển trên vòng theo một chuỗi liên tiếp các liên kết Point to Point giữa các repeater. Mạng hình vòng có ưu, nhược điểm tương tự như mạng hình sao, tuy nhiên mạng hình vòng đòi hỏi giao thức truy nhập mạng phức tạp hơn mạng hình sao. Ngoài ra còn có các kết nối hỗn hợp giữa các kiến trúc mạng trên như: Star Bus, Star Ring Phần 2: Tầng mạng (NETWORK layer) Giới thiệu: Chúng ta đã xem xét cách thức xây dựng và vận hành của các mạng đơn lẻ sử dụng các nối kết điểm điểm, các đường truyền chia sẻ và các bộ hoán chuyển (switch). Vấn đề phát sinh là có nhiều người muốn xây dựng hệ thống mạng riêng của họ theo nhiều kỹ thuật khác nhau nhưng lại muốn giao tiếp với nhau mà không quan tâm rằng họ đang hoạt động trên các hệ thống không đồng nhất. Chương này sẽ trình bày về cách thức để nối kết những mạng không đồng nhất lại với nhau. Có hai vấn đề quan trọng cần phải quan tâm khi nối kết các mạng: tính không đồng nhất (heterogeneity) và phạm vi (scale) khác nhau của chúng. Giải thích một cách đơn giản, tính không đồng nhất là khi người dùng trên hai mạng khác kiểu nhau muốn giao tiếp với nhau. Phức tạp hơn một chút, ta có thể thấy việc nối kết các host trên các mạng khác nhau có thể sẽ đòi hỏi việc duyệt qua nhiều mạng trung gian, mà các mạng trung gian này lại có thể có kiểu khác nhau. Chúng có thể là mạng Ethernet, Token Ring hay mạng dạng điểm nối điểm, hoặc nhiều kiểu mạng hoán chuyển (switch) khác nhau, và chúng lại sử dụng các phương thức đánh địa chỉ riêng, các phương pháp truy cập đường truyền riêng và cả mô hình dịch vụ riêng nữa. Thách thức đối với vấn đề không đồng nhất là làm sao cung cấp cho người dùng một dịch vụ nối kết host-host dễ hiểu xuyên qua mớ hỗn độn các mạng không đồng nhất. Để hiểu về vấn đề phạm vi mạng, ta lấy một ví dụ có giá trị là sự phát triển của mạng Internet, mạng có tốc độ phát triển gần gấp đôi sau mỗi năm trong vòng 20 năm qua. Kiểu phát triển chóng mặt này buộc chúng ta phải đối mặt với nhiều thách thức. Một trong số đó là việc vạch đường: Làm sao để tìm ra một đường đi hữu hiệu xuyên qua một mạng gồm cả triệu nút mạng? Thêm một vấn đề có liên quan đến vạch đường là phương pháp đánh địa chỉ, là cách gán cho mỗi nút trên mạng một định danh duy nhất. Tầng mạng có nhiệm vụ đưa các gói tin từ máy gởi qua các chặn đường để đến được máy nhận. Để đến được đích đến, gói tin có thể phải đi từng bước một qua nhiều router trung gian. Điều này thì trái ngược với tầng liên kết dữ liệu vốn chỉ chịu trách nhiệm truyền tải các khung đi từ đầu này đến đầu kia của một kênh truyền vật lý. Để thực hiện được nhiệm vụ này, tầng mạng phải biết được hình trạng của mạng đường trục (subnet) và chọn đường thích hợp để cho gói tin đi. Nó phải chú ý đến việc chọn đường sao cho tránh được tình trạng tắc nghẽn trên một số đường truyền và router trong khi số khác thì đang rãnh rỗi. Các giải thuật chọn đường: Giới thiệu: Vạch đường về bản chất là một bài toán trong lý thuyết đồ thị. Hình 6.4 thể hiện một đồ thị biểu diễn cho một mạng. Hình 2.1 Mạng được biểu diễn như một đồ thị Các nút trong đồ thị (được đánh dấu từ A đến F) có thể là các host, switch, router hoặc là các mạng con. Ở đây chúng ta tập trung vào một trường hợp các nút là các router. Các cạnh của đồ thị tương ứng với các đường nối kết mạng. Mỗi cạnh có một chi phí đính kèm, là thông số chỉ ra cái giá phải trả khi lưu thông trên nối kết mạng đó. Vấn đề cơ bản của việc vạch đường là tìm ra đường đi có chi phí thấp nhất giữa hai nút mạng bất kỳ, trong đó chi phí của đường đi được tính bằng tổng chi phí khi đi qua tất cả các cạnh làm thành đường đi đó. Nếu không có một đường đi giữa hai nút, thì độ dài đường đi giữa chúng được xem như bằng vô cùng. Mục tiêu của giải thuật chọn đường: Xác định đướng đi nhanh chóng, chính xác. Khả năng thích nghi được với những thay đổi về hình trạng mạng. Khả năng thích nghi được với những thay đổi về tải đường truyền. Khả năng tránh được các nối kết bị tắt nghẽn tạm thời Chi phí tính toán để tìm ra được đường đi phải thấp Phân loại giải thuật chọn đường: Giải thuật chọn đường có thể được phân thành những loại sau: Chọn đường tập trung (Centralized routing): Trong mạng có một Trung tâm điều khiển mạng (Network Control Center) chịu trách nhiệm tính toán và cập nhật thông tin về đường đi đến tất cả các điểm khác nhau trên toàn mạng cho tất cả các router. Chọn đường phân tán (Distributed routing): Trong hệ thống này, mỗi router phải tự tính toán tìm kiếm thông tin về các đường đi đến những điểm khác nhau trên mạng. Để làm được điều này, các router cần phải trao đổi thông tin quan lại với nhau. Chọn đường tĩnh (Static routing): Trong giải thuật này, các router không thể tự cập nhật thông tin về đường đi khi hình trạng mạng thay đổi. Thông thường nhà quản mạng sẽ là người cập nhật thông tin về đường đi cho router. Chọn đường động (Dynamic routing): Trong giải thuật này, các router sẽ tự động cập nhật lại thông tin về đường đi khi hình trạng mạng bị thay đổi. Các giải thuật tìm đường tối ưu: Đường đi tối ưu từ A đến B là đường đi “ngắn” nhất trong số các đường đi có thể. Tuy nhiên khái niệm “ngắn” nhất có thể được hiểu theo nhiều ý nghĩa khác nhau tùy thuộc vào đơn vị dùng để đo chiều dài đường đi. Đối với các router, các đại lượng sau có thể được sử dụng để đo độ dài đường đi: Số lượng các router trung gian phải đi qua (HOP) Độ trì quản trung bình của các gói tín Cước phí truyền tin Mỗi giải thuật chọn đường trước tiên phải chọn cho mình đơn vị đo chiều dài đường đi. Để xác định được đường đi tối ưu, các giải thuật chọn đường sử dụng phương pháp đồ thị để tính toán. Trước tiên, nó mô hình hóa hình trạng mạng thành một đồ thị có các đặc điểm như sau: Nút là các router. Cạnh nối liền 2 nút là đường truyền nối hai router. Trên mỗi cạnh có giá đó là chiều dài đường đi giữa 2 router thông qua đường truyền nối hai router . Chiều dài đường đi từ nút A đến nút B là tổng tất cả các giá của các cạnh nằm trên đường đi. Nếu không có đường đi giữa 2 router thì xem như giá là vô cùng. Trên đồ thị này sẽ thực hiện việc tính toán tìm đường đi ngắn nhất. Hình 2.2 Mô hình hóa mạng thành đồ thị Giải thuật tìm đường đi ngắn nhất Dijkstra: Mục đích là để tìm đường đi ngắn nhất từ một nút cho trước trên đồ thị đến các nút còn lại trên mạng. Giải thuật được mô tả như sau: Gọi: S là nút nguồn cho trước N: là tập hợp tất cả các nút đã xác định được đường đi ngắn nhất từ S. Di: là độ dài đường đi ngắn nhất từ nút nguồn S đến nút i. lij: là giá của cạnh nối trực tiếp nút i với nút j, sẽ là ∞ nếu không có cạnh nối trực tiếp giữa i và j. Pj là nút cha của của nút j. Bước 1: Khởi tạo N={S}; Ds=0; Với i≠S: Di=lsi , Pi=S Bước 2: Tìm nút gần nhất kế tiếp Tìm nút i không thuộc N thoả Di= min (Dj) với j không thuộc N Thêm nút i vào N. Nếu N chứa tất cả các nút của đồ thị thì dừng. Ngược lại sang Bước 3 Bước 3: Tính lại giá đường đi nhỏ nhất Với mỗi nút j không thuộc N: Tính lại Dj= min{ Dj, Di+ lij} ; Pj=i; Trở lại Bước 2 Ví dụ: Cho mạng có hình trạng như đồ thị hình H6.6: Tìm đường đi ngắn nhất từ nút 1 đến các nút còn lại. Áp dụng giải thuật ta có: S=1 Các bước thực hiện được mô tả như sau: Lần lặp N D2 D3 D4 D5 D6 P2 P3 P4 P5 P6 Khởi tạo {1} 3 2 5 ∞ ∞ 1 1 1 1 1 1 {1,3} 3 2 4 ∞ 3 1 1 3 1 3 2 {1,3,2} 3 4 7 3 1 3 2 3 3 {1,3,2,6} 4 5 3 3 6 3 4 {1,3,2,6,4} 4 5 3 6 5 {1,3,2,6,4,5} 5 6 Từ kết quả trên ta vẽ được cây có đường đi ngắn nhất từ nút số 1 đến các nút còn lại như hình 2.3 . Từ cây đường đi ngắn nhất này, ta xác định được rằng: để đi đến các router router 4, 5, 6, bước kế tiếp router 1 cần gởi gói tin đến là router số 3 (next hop). Chú ý, đường ngắn nhất này chỉ đúng theo hướng từ nút số 1 về các nút còn lại và chỉ đúng cho nút số 1 mà thôi. Thông thường giải thuật Dijkstra được sử dụng theo mô hình chọn đường tập trung. Trong đó, Trung tâm điều khiển mạng sẽ tìm cây đường đi ngắn nhất cho từng router trên mạng và từ đó xây dựng bảng chọn đường tối ưu cho tất cả các router. Hình 2.3 Đường đi ngắn nhất từ nút 1 Giải thuật chọn đường tối ưu Ford-Fulkerson: Mục đích của giải thuật này là để tìm đường đi ngắn nhất từ tất cả các nút đến một nút đích cho trước trên mạng. Giải thuật được mô tả như sau: Gọi od là nút đích cho trước oDi là chiều dài đường đi ngăn nhất từ nút i đến nút d. oCi là nút con của nút i Bước 1: Khởi tạo: oGán Dd = 0; oVới i≠d: gán Di= ∞; Ci= -1; Bước 2: Cập nhật giá đường đi ngắn nhất từ nút i đến nút d oDi= min{ lij+ Dj} với j≠i => Ci = j; oLặp lại cho đến khi không còn Di nào bị thay đổi giá trị Ví dụ, cho sơ đồ mạng có hình trạng như đồ thị hình H6.8. Hãy tìm đường đi ngắn nhất từ nút khác trên đồ thị đến nút 6. Áp dụng giải thuật ta có: d=6 Các bước thực hiện được mô tả như sau: Lần lặp D1 D2 D3 D4 D5 C1 C2 C3 C4 C5 Khởi tạo ∞ ∞ ∞ ∞ ∞ -1 -1 -1 -1 -1 1 ∞ ∞ 1 3 2 -1 -1 6 3 6 2 3 4 1 3 2 3 4 6 3 6 3 3 4 1 3 2 3 4 6 3 6 Từ kết quả trên ta vẽ lại được cây đường đi ngắn nhất từ các nút khác nhau về nút đích số 6 như hình 2.4. Cây này cho phép xác định đường đi tối ưu từ những nút khác nhau về nút số 6. Chẳng hạn tại nút 1, để đi về nút số 6 thì bước kế tiếp phải đi là nút số 3. Tương tự, tại nút 2, để đi về nút số 6 thì bước kế tiếp phải đi là nút số 4. Giải thuật này được sử dụng theo mô hình phân tán. Ở đó mỗi router sẽ tự tính toán, tìm cây có đường đi ngắn nhất từ các nút khác về nó. Từ đó suy ra đường đi tối ưu cho các nút khác đến nó và gởi các đường đi này đến từng nút trên mạng. Hình 2.4 Cây đường đi ngắn nhất về nút 6 Giải pháp vạch đường Vector Khoảng cách (Distance Vector): Ý tưởng của Distance-Vector như sau: Mỗi nút thiết lập một mảng một chiều (vector) chứa khoảng cách (chi phí) từ nó đến tất cả các nút còn lại và sau đó phát vector này đến tất cả các nút láng giềng của nó. Giả thiết đầu tiên trong Distance-Vector là: mỗi nút phải biết được chi phí của các đường nối từ nó đến tất cả các nút láng giềng có đường nối kết trực tiếp với nó. Một nối kết bị đứt (down) sẽ được gán cho chi phí có giá trị vô cùng. Để xem xét giải thuật vạch đường Distance-Vector hoạt động như thế nào, cách dễ nhất là xem xét đồ thị được cho như trong hình Hình 2.5 Hình 2.5 Một mạng làm ví dụ trong giả