Giáo trình môn Mạng máy tính (Phần 2) - Ngô Bá Hùng

110 trang ngocly 1930

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình môn Mạng máy tính (Phần 2) - Ngô Bá Hùng", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_mon_mang_may_tinh_phan_2_ngo_ba_hung.pdf

Nội dung text: Giáo trình môn Mạng máy tính (Phần 2) - Ngô Bá Hùng

Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 Chương 5: MẠNG NỘI BỘ & LỚP CON ĐIỀU KHIỂN TRUY CẬP Mục đích Chương này nhằm giới thiệu với người học những nội dung sau: • Các phương chia sẻ đường truyền chung giữa các máy tính trong một mạng cục bộ như: các phương pháp chia kênh, các phương pháp truy cập đường truyền ngẫu nhiên và các phương pháp phân lượt truy cập đường truyền. • Giới thiệu chi tiết về nguyên tắc hoạt động của các chuẩn mạng cục bộ như họ các chuẩn mạng Ethernet, FDDI và mạng không dây Yêu cầu Sau khi học xong chương này, người học phải có được các khả năng sau: • Trình bày được sự khác biệt cơ bản về cách thức chia sẻ đường truyền chung giữa các máy tính trong các phương pháp chia kênh, truy cập đường truyền ngẫu nhiên và phân lượt truy cập đường truyền. • Trình bày được nguyên tắc chia sẻ đường truyền chung giữa các máy tính theo các phương pháp FDMA, TDMA, CDMA, ALOHA, CSMA, CAMA/CD, Token Passing, • Trình bày được những đặc điểm và nguyên tắc hoạt động của các chuẩn thuộc họ mạng Ethernet, mạng FDDI và chuẩn mạng không dây 802.11 Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 61
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 5.1 Tổng quan về LAN Như đã trình bày trong phần 2.1, theo tiêu chí đánh giá là khoảng cách địa lý thì người ta thường phân loại mạng máy tính thành ba kiểu: Mạng nội bộ - Local Area Network (LAN) Mạng đô thị - Metropolitan Area Network (MAN) Mạng diện rộng - Wide Area Network (WAN) Trong thực tế, LAN và WAN thường được cài đặt nhất. Mạng LAN được sử dụng để nối kết một dãi rộng các thiết bị trong một phạm vi hẹp, ví dụ: trên cùng một tầng, một tòa nhà hay một khuôn viên (thường không vượt quá 10Km). Ngày nay, LAN là loại mạng được sử dụng rất phổ biến trong mọi lĩnh vực của xã hội. Người ta thường nghĩ đến LAN như là mạng có thông lượng cao, độ trì hoãn thấp. Hiện tại có rất nhiều công nghệ xây dựng mạng LAN mà chúng ta sẽ xem xét đến ngay sau đây. Nhiều chuẩn mạng LAN đã được phát triển trong đó Ethernet và FDDI là phổ biến nhất. Người ta thường gọi chung họ các chuẩn mạng LAN là IEEE 802. Về góc độ kỹ thuật, LAN có các tính chất quan trọng sau: Tất cả các host trong mạng LAN cùng chia sẻ đường truyền chung. Do đó chúng hoạt động dựa trên kiểu quảng bá (broadcast). Không yêu cầu phải có hệ thống trung chuyển (routing/switching) trong một LAN đơn. Thông thường, một mạng LAN được định nghĩa dựa trên các thông số sau: Hình thái (topology): Chỉ ra kiểu cách mà các host trong mạng được đấu nối với nhau. Đường truyền chia sẻ (xoắn đôi, đồng trục, cáp quang): Chỉ ra các kiểu đường truyền mạng (network cables) được dùng để đấu nối các host trong LAN lại với nhau. (Xin xem lại mô tả chi tiết các kiểu đường truyền trong chương Tầng Vật Lý). Kỹ thuật truy cập đường truyền (Medium Access Control - MAC): Chỉ ra cách thức mà các host trong mạng LAN sử dụng để truy cập và chia sẻ đường truyền mạng. MAC sẽ quản trị việc truy cập đến đường truyền trong LAN và cung cấp cơ sở cho việc định danh các tính chất của mạng LAN theo chuẩn IEEE. 5.2 Hình thái mạng Hình thái mạng sẽ xác định hình dáng tổng quát của một mạng. Hiện tại, người ta đã định nghĩa ra được nhiều hình thái mạng khác nhau tương ứng với những tính chất đặc thù của chúng. Hình thái mạng là tiêu chí bắt buộc dùng để xây dựng mạng LAN và nó chủ yếu quan tâm đến việc làm cho mạng được liên thông, che dấu chi tiết về các thiết bị thực đối với người dùng. 5.2.1 Mạng hình sao H5.1 Sơ đồ mạng hình sao Tất cả các máy tính trong mạng được đấu nối tới một thiết bị tập trung tín hiệu trung tâm. Thành phần trung tâm của mạng được gọi là Hub. Phương thức hoạt động của mạng hình sao như sau: Mọi máy tính đều phát tín hiệu ra Hub và Hub phát lại tín hiệu vào đến tất cả các đầu ra. Mỗi máy tính có một nối kết riêng lẻ đến Hub Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 62
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 5.2.2 Mạng hình vòng H5.2 Sơ đồ mạng hình vòng Không có thiết bị trung tâm trong sơ đồ nối mạng hình vòng. Đường nối kết mạng sẽ đi trực tiếp từ một máy tính đến máy tính khác. Thực tế, có một đoạn cable ngắn nối máy tính với vòng. 5.2.3 Mạng hình bus H5.3 Sơ đồ mạng hình bus Trong sơ đồ mạng hình bus, người ta dùng một dây cáp (cable) đơn nối kết toàn bộ LAN. Mỗi máy tính có một đầu nối đến cáp được chia sẻ. Với một đường truyền chia sẻ như thế thì sẽ có khả năng đụng độ xảy ra khi các máy tính cùng phát tín hiệu ra đường truyền cùng một lúc. Do đó, phải có giải pháp làm cho các máy tính hoạt động đồng bộ với nhau nhằm cho phép chỉ một máy tính truyền thông tin tại một thời điểm. 5.3 Lớp con MAC (Media Access Control Sublayer) Như đã trình bày ở trên, chương này trình bày về mạng LAN – mạng dạng truyền quảng bá và các giao thức truyền quảng bá của nó. Trong bất kỳ mạng dạng quảng bá nào, vấn đề then chốt luôn là cách thức người ta quyết định ai có quyền truy cập kênh truyền tại một thời điểm. Để làm rõ vấn đề hơn, hãy xem xét ví dụ sau: Có sáu người đang họp thông qua hệ thống điện thoại, mọi người đều được nối kết để có thể nghe và nói với những người khác. Khi một người ngừng nói mà có hai người hoặc nhiều hơn cùng phát biểu tiếp sẽ tạo ra tình trạng lộn xộn. Trong các cuộc họp dạng gặp mặt trực tiếp, tình trạng lộn xộn này có thể được giải quyết bằng cách đưa tay xin phát biểu. Nhưng trong hệ thống hội thảo thông qua điện thoại này, khi mà đường truyền rảnh, việc quyết định ai sẽ nói tiếp có vẻ khó làm hơn. Đã có nhiều giao thức dùng giải quyết vấn đề trên. Và chúng chính là nội dung trình bày của phần này. Nói một cách khác, các kênh truyền dạng quảng bá thỉnh thoảng còn được gọi là các kênh đa truy cập (multiaccess channels) hay là các kênh truy cập ngẫu nhiên (random access channels). Các giao thức được sử dụng để quyết định ai có quyền truy cập đường truyền quảng bá trước được gom vào trong một lớp con của tầng liên kết dữ liệu gọi là lớp con MAC. Lớp con MAC là đặc biệt quan trọng trong mạng LAN, do nhiều mạng LAN sử dụng đường truyền dạng quảng bá như là phương tiện truyền thông nền tảng. Các mạng WAN, theo xu hướng ngược lại, lại dùng các nối kết dạng điểm-điểm (ngoại trừ các mạng dùng vệ tinh). Về cơ bản, có ba phương pháp điều khiển truy cập đường truyền: Chia kênh, truy cập ngẫu nhiên (Random Access) và phân lượt (“Taking-turns”). Giải thích cụ thể về ba phương pháp điều khiển truy cập đường truyền trên sẽ được trình bày ngay sau đây. Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 63
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 5.3.1 Phương pháp chia kênh Ý tưởng chung của phương pháp này là: đường truyền sẽ được chia thành nhiều kênh truyền, mỗi kênh truyền sẽ được cấp phát riêng cho một trạm. Có ba phương pháp chia kênh chính: FDMA, TDMA, CDMA. 5.3.1.1 Chia tần số (FDMA – Frequency Division Multiple Access) Một phương thức truyền thống để chia sẻ một kênh truyền đơn cho nhiều người dùng cạnh tranh là Chia tần số (FDMA). Phổ của kênh truyền được chia thành nhiều băng tần (frequency bands) khác nhau. Mỗi trạm được gán cho một băng tần cố định. Những trạm nào được cấp băng tần mà không có dữ liệu để truyền thì ở trong trạng thái nhàn rỗi (idle). Ví dụ: Một mạng LAN có sáu trạm, các trạm 1, 3, 4 có dữ liệu cần truyền, các trạm 2, 5, 6 nhàn rỗi. H5.4 Mạng FDMA Nhận xét: Do mỗi người dùng được cấp một băng tần riêng, nên không có sự đụng độ xảy ra. Khi chỉ có số lượng người dùng nhỏ và ổn định, mỗi người dùng cần giao tiếp nhiều thì FDMA chính là cơ chế điều khiển truy cập đường truyền hiệu quả. Tuy nhiên, khi mà lượng người gởi dữ liệu là lớn và liên tục thay đổi hoặc đường truyền vượt quá khả năng phục vụ thì FDMA bộc lộ một số vấn đề. Nếu phổ đường truyền được chia làm N vùng và có ít hơn N người dùng cần truy cập đường truyền, thì một phần lớn phổ đường truyền bị lãng phí. Ngược lại, có nhiều hơn N người dùng có nhu cầu truyền dữ liệu thì một số người dùng sẽ phải bị từ chối không có truy cập đường truyền vì thiếu băng thông. Tuy nhiên, nếu lại giả sử rằng số lượng người dùng bằng cách nào đó luôn được giữ ổn định ở con số N, thì việc chia kênh truyền thành những kênh truyền con như thế tự thân là không hiệu quả. Lý do cơ bản ở đây là: nếu có vài người dùng rỗi, không truyền dữ liệu thì những kênh truyền con cấp cho những người dùng này bị lãng phí. Có thể dễ dàng thấy được hiệu năng nghèo nàn của FDMA từ một phép tính theo lý thuyết xếp hàng đơn giản. Bắt đầu là thời gian trì hoãn trung bình T trong một kênh truyền có dung lượng C bps, với tỉ lệ đến trung bình là λ khung/giây, mỗi khung có chiều dài được chỉ ra từ hàm phân phối mũ với giá trị trung bình là 1/µ bit/khung. Với các tham số trên ta có được tỉ lệ phục vụ là µC khung/giây. Từ lý thuyết xếp hàng ta có: 1 T = µC −λ Ví dụ: nếu C = 100 Mbps, 1/µ = 10000 bits và λ = 5000 khung/giây thì T = 200 µs. Bây giờ nếu ta chia kênh lớn này thành N kênh truyền nhỏ độc lập, mỗi kênh truyền nhỏ có dung lượng C/N bps. Tỉ lệ trung bình các khung đến các kênh truyền nhỏ bây giờ là λ/N. Tính toán lại T chúng ta có: 1 N TFDMA = µ (C / N )−(λ / N ) = µC −λ = NT Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 64
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 Thời gian chờ đợi trung bình trong các kênh truyền con sử dụng FDMA là xấu hơn gấp N lần so với trường hợp ta sắp xếp cho các khung được truyền tuần tự trong một kênh lớn. 5.3.1.2 Chia thời gian (TDMA – Time Division Multiple Access) Trong phương pháp này, các trạm sẽ xoay vòng (round) để truy cập đường truyền. Vòng ở đây có thể hiểu là vòng thời gian. Một vòng thời gian là khoảng thời gian đủ để cho tất cả các trạm trong LAN đều được quyền truyền dữ liệu. Qui tắc xoay vòng như sau: một vòng thời gian sẽ được chia đều thành các khe (slot) thời gian bằng nhau, mỗi trạm sẽ được cấp một khe thời gian – đủ để nó có thể truyền hết một gói tin. Những trạm nào tới lượt được cấp cho khe thời gian của mình mà không có dữ liệu để truyền thì vẫn chiếm lấy khe thời gian đó, và khoảng thời gian bị chiếm này được gọi là thời gian nhàn rỗi (idle time). Tập hợp tất cả các khe thời gian trong một vòng được gọi lại là khung (frame). Ví dụ: H5.5 Mạng TDMA Mạng LAN dùng cơ chế truy cập đường truyền TDMA trên có sáu trạm. Các trạm 1, 3, 4 có dữ liệu cần truyền. Các trạm 2, 5, 6 nhàn rỗi. Chúng ta cũng áp dụng cùng một nhận xét về mạng TDMA như mạng FDMA. Mỗi người dùng được cấp phát một khe thời gian. Và nếu người dùng không sử dụng khe thời gian này để truyền dữ liệu thì thời gian sẽ bị lãng phí. 5.3.1.3 Kết hợp giữa FDMA và TDMA Trong thực tế, hai kỹ thuật TDMA và FDMA thường được kết hợp sử dụng với nhau, ví dụ như trong các mạng điện thoại di động. Các điện thoại di động TDMA sử dụng các kênh 30 KHz, mỗi kênh lại được chia thành ba khe thời gian. Một thiết bị cầm tay sử dụng một khe thời gian cho việc gởi và một khe khác cho việc nhận dữ liệu. Chẳng hạn như các hệ thống: Cingular (Nokia 8265, TDMA 800/ 1900 MHz, AMPS 800 mHz ), AT&T Wireless. Hệ thống GSM sử dụng các kênh 200 KHz được chia thành 8 khe thời gian. Một thiết bị cầm tay sẽ sử dụng một khe thời gian trong hai kênh khác nhau để gởi và nhận thông tin. Các hệ thống Cingular, T-Mobile, AT&T đang chuyển sang dùng kỹ thuật này. H5.6 Kết hợp giữa TDMA và FDMA 5.3.1.4 Phân chia mã (CDMA – Code Division Multiple Access) CDMA hoàn toàn khác với FDMA và TDMA. Thay vì chia một dãy tần số thành nhiều kênh truyền băng thông hẹp, CDMA cho phép mỗi trạm có quyền phát dữ liệu lên toàn bộ phổ tần của đường truyền lớn tại mọi thời điểm. Các cuộc truy cập đường truyền xảy ra đồng thời sẽ được tách biệt với nhau bởi kỹ thuật mã hóa. CDMA cũng xóa tan lo lắng cho rằng những khung dữ liệu bị đụng độ trên đường truyền sẽ bị biến dạng. Thay vào đó CDMA chỉ ra rằng nhiều tín hiệu đồng Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 65
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 thời sẽ được cộng lại một cách tuyến tính! Kỹ thuật CDMA thường được sử dụng trong các kênh truyền quảng bá không dây (mạng điện thoại di động, vệ tinh ). Trước khi đi vào mô tả giải thuật CDMA, hãy xem xét một ví dụ gần giống như sau: tại một phòng đợi trong sân bay có nhiều cặp hành khách đang chuyện trò. TDM có thể được so sánh với cảnh tượng: tất cả mọi người đều đứng giữa phòng, chờ đến lượt mình được phát biểu. FDM thì giống như cảnh tượng: mỗi một cặp được sắp vào một ô nói chuyện riêng. Còn CDMA lại giống như cảnh: mọi người đều đứng ngay trong phòng đợi, nói chuyện đồng thời, nhưng mỗi cặp chuyện trò sẽ sử dụng một ngôn ngữ riêng. Cặp nói tiếng Pháp chỉ líu lo với nhau bằng tiếng Pháp, bỏ qua mọi tiếng động không phải là tiếng Pháp và coi đó như là tiếng ồn. Vì thế, vấn đề then chốt trong CDMA là khả năng rút trích ra được tín hiệu mong muốn trong khi từ chối mọi thứ khác và coi đó là tiếng ồn ngẫu nhiên. Trong CDMA, thời gian gởi một bit (bit time) lại được chia thành m khoảng nhỏ hơn, gọi là chip. Thông thường, có 64 hay 128 chip trên một bit, nhưng trong ví dụ phía dưới, chúng ta dùng 8 chip cho đơn giản. Nhiều người dùng đều chia sẻ chung một băng tần, nhưng mỗi người dùng được cấp cho một mã duy nhất dài m bit gọi là dãy chip (chip sequence). Dãy chip này sẽ được dùng để mã hóa và giải mã dữ liệu của riêng người dùng này trong một kênh truyền chung đa người dùng. Ví dụ, sau đây là một dãy chip: (11110011). Để gởi bit 1, người dùng sẽ gởi đi dãy chip của mình. Còn để gởi đi bit 0, người dùng sẽ gởi đi phần bù của dãy chip của mình. Ví dụ với dãy chip trên, khi gởi bit 1, người dùng sẽ gởi 11110011; khi gởi bit 0 thì người dùng sẽ gởi 00001100. Để tiện cho việc minh họa, chúng ta sẽ sử dụng các ký hiệu lưỡng cực sau: bit 0 được ký hiệu là - 1, bit 1 được ký hiệu là +1. Cũng cần phải đưa ra một định nghĩa mới: tích trong (inner product): Tích trong của hai mã S và T, ký hiệu là S•T, được tính bằng trung bình tổng của tích các bit nội tại tương ứng của hai mã này. 1 m S • T = ∑ S i T i m i =1 Ví dụ: S = +1+1+1−1−1+1+1−1 T = +1+1+1+1−1−1+1−1 +1+1+1+ (−1) +1+ (−1) +1+1 1 S •T = = 8 2 Bây giờ ta xem xét cách thức cấp phát chuỗi chip cho các trạm, sao cho không gây ra lẫn lộn thông tin giữa các trạm với nhau. Định nghĩa: Hai mã S và T có cùng chiều dài m bits được gọi là trực giao khi: S•T = 0. Ví dụ: S = +1+1−1−1−1−1−1+1 T = −1−1+1−1−1−1+1+1 (−1) + (−1) + (−1) +1+1+1+ (−1) +1 S •T = = 0 8 Nếu các người dùng trong hệ thống có các mã trực giao với nhau thì họ có thể cùng tồn tại và truyền dữ liệu một cách đồng thời với khả năng bị giao thoa dữ liệu là ít nhất. Qui ước: Gọi Di là bit dữ liệu mà người dùng i muốn mã hóa để truyền trên mạng. Ci là chuỗi chip (mã số) của người dùng i. Sau đây là cách thức mã hóa tín hiệu để gởi lên đường truyền và giải mã để lấy dữ liệu đó ra: Tín hiệu được mã của người dùng i: Zi = Di x Ci Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 66
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 Tín hiệu tổng hợp được gởi trên đường truyền: n Z = ∑ Z i i=1 với n là tổng số người dùng gởi tín hiệu lên đường truyền tại cùng thời điểm Giải mã: Dữ liệu mà người dùng i lấy về từ tín hiệu tổng hợp chung: Di = Z • Ci Nếu Di > “ngưỡng”, coi nó là 1, ngược lại coi nó là -1 Ví dụ: Hệ thống có 4 người dùng A, B, C, D. Các mã số tương ứng của họ như sau: Nếu ký hiệu theo kiểu lưỡng cực thì: Để ý các mã số A, B, C, D là trực giao! Có sáu ví dụ: 1) Chỉ có người dùng C gởi bit 1: 2) B gởi bit 1, C gởi bit 1 3) A gởi bit 1, B gởi bit 0 4) A, C đều gởi bit 1, B gởi bit 0 5) A, B, C, D đều gởi bit 1 6) A, B, D gởi bit 1, C gởi bit 0 Ta tính toán được các mã tổng hợp gởi lên đường truyền như sau: Bây giờ, ta tính được dữ liệu nguyên thủy của người dùng ở trạm C, sau khi đã rút trích ra từ mã tổng hợp như sau: Nhận xét: Đầu tiên, chúng ta phải giả sử rằng tất cả các dãy chip được đồng bộ hóa để được gởi nhận cùng thời điểm. Nhưng trong thực tế, kiểu đồng bộ hóa như vậy là không thể có được. Những gì người ta có thể làm được để đồng bộ hóa là: người gởi và người nhận đồng bộ hóa với nhau bằng cách cho người gởi gởi một dãy chip được định nghĩa trước, dãy này phải đủ dài để cho bên nhận có thể theo kịp bên gởi. Tất cả các cuộc truyền nhận khác được xem như là nhiễu ngẫu nhiên. Người ta chứng minh được rằng, chuỗi chip càng dài thì xác suất phát hiện ra chuỗi này một cách chính xác là càng cao với sự hiện diện của nhiễu. Cũng cần phải giả thiết rằng: bên nhận biết chính xác bên gởi là ai. Tuy trong thực tế, cần phải trung thực mà nói rằng: đặt giả thiết thì dễ hơn là làm. Nhưng hãy tin tưởng là CDMA có nhiều chi tiết phức tạp hơn và thông minh hơn để làm được chuyện đó. Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 67
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 5.3.2 Phương pháp truy cập đường truyền ngẫu nhiên (Random Access) Trong phương pháp này, người ta để cho các trạm tự do tranh chấp đường truyền chung để truyền từng khung dữ liệu một. Nếu một trạm cần gởi một khung, nó sẽ gởi khung đó trên toàn bộ dải thông của kênh truyền. Sẽ không có sự phối hợp trình tự giữa các trạm. Nếu có hơn hai trạm phát cùng một lúc, “đụng độ” (collision) sẽ xảy ra, các khung bị đụng độ sẽ bị hư hại. Giao thức truy cập đường truyền ngẫu nhiên được dùng để xác định: Làm thế nào để phát hiện đụng độ. Làm thế nào để phục hồi sau đụng độ. Ví dụ về các giao thức truy cập ngẫu nhiên: slotted ALOHA và pure ALOHA, CSMA và CSMA/CD, CSMA/CA. 5.3.2.1 ALOHA Vào những năm 1970, Norman Abramson cùng các đồng sự tại Đại học Hawaii đã phát minh ra một phương pháp mới ưu hạng dùng để giải quyết bài toán về cấp phát kênh truyền. Sau đó công việc của họ tiếp tục được mở rộng bởi nhiều nhà nghiên cứu khác. Mặc dù công trình của Abramson, được gọi là hệ thống ALOHA, sử dụng hệ thống truyền quảng bá trên sóng radio mặt đất, nhưng ý tưởng cơ sở của nó có thể áp dụng cho bất kỳ hệ thống nào trong đó những người dùng không có phối hợp với nhau sẽ tranh chấp sử dụng đường truyền chung duy nhất. Ở đây, chúng ta sẽ thảo luận về hai phiên bản của ALOHA: pure (thuần túy) và slotted (được chia khe). 5.3.2.1.1 Slotted ALOHA Thời gian được chia thành nhiều slot có kích cỡ bằng nhau (bằng thời gian truyền một khung). Một trạm muốn truyền một khung thì phải đợi đến đầu slot thời gian kế tiếp mới được truyền. Dĩ nhiên là sẽ xảy ra đụng độ và khung bị đụng độ sẽ bị hư. Tuy nhiên, dựa trên tính phản hồi của việc truyền quảng bá, trạm phát luôn có thể theo dõi xem khung của nó phát đi có bị hủy hoại hay không bằng cách lắng nghe kênh truyền. Những trạm khác cũng làm theo cách tương tự. Trong trường hợp vì lý do nào đó mà trạm không thể dùng cơ chế lắng nghe đường truyền, hệ thống cần yêu cầu bên nhận trả lời một khung báo nhận (acknowledgement) cho bên phát. Nếu phát sinh đụng độ, trạm phát sẽ gởi lại khung tại đầu slot kế tiếp với xác suất p cho đến khi thành công. Ví dụ minh họa: Có 3 trạm đều muốn truyền một khung thông tin. H5.7 Minh họa giao thức Slotted ALOHA Do sẽ có đụng độ mà mất khung thông tin, một câu hỏi đặt ra là: đâu là tỉ suất truyền khung thành công của các trạm trong mạng? Giả sử có N trạm muốn truyền dữ liệu, mỗi trạm truyền khung thông tin của mình trong một slot với xác suất p. Xác suất để một trạm trong N trạm truyền thành công S(p) được tính như sau: Sp()=−Np(1 p)N −1 1 1 N −1 Khi p = N , S(p) đạt giá trị cực đại (1 − N ) 5.3.2.1.2 Pure ALOHA Kỹ thuật Pure ALOHA đơn giản hơn Slotted ALOHA do không có sự đồng bộ hóa giữa các trạm. Mỗi khi muốn truyền một khung thông tin, trạm sẽ truyền nó ngay mà không cần đợi đến đầu của Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 68
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 slot thời gian kế tiếp. Vì thế xác xuất bị đụng độ tăng thêm! Nghĩa là khung thông tin được gởi tại thời điểm t0 sẽ đụng độ với những khung được gởi trong khoảng thời gian [t0-1, t0+1]. H5.8 Minh họa giao thức Pure ALOHA Gọi P là xác xuất của một sự kiện nào đó, ta có những phân tích sau: P(nút i truyền thành công) = P(để nút i truyền) × P(không có nút nào khác truyền trong khoảng [t -1,t ]) . 0 0 × P(không có nút nào khác truyền trong khoảng [t t +1]) 0, 0 = pp(1 −−) NN−11(1 p) − S(p) = P(một nút bất kỳ trong N nút truyền thành công) = Np(1 −−p) NN−11(1 p) − Những phân tích vừa nêu giả sử rằng luôn có thường trực N trạm trong mạng. Và trong trường hợp tối ưu, mỗi trạm thử truyền vơi xác suất 1/N. Trong thực tế, số lượng các trạm thường trực trong mạng luôn thay đổi. Giả sử chúng ta có tổng cộng m trạm làm việc. n trạm là thường trực trên mạng, mỗi trạm thường trực trên mạng sẽ cố gởi khung thông tin với xác suất cố định p. m-n trạm còn lại là không thường trực, và chúng có thể gởi khung thông tin với xác suất pa, với pa có thể nhỏ hơn p. Nhận xét chung về ALOHA: Hiệu năng thấp do không có thăm dò đường truyền trước khi gởi khung, dẫn đến việc mất nhiều thời gian cho việc phát hiện đụng độ và phục hồi sau đụng độ. Hoạt động theo kiểu ALOHA có khả năng dẫn đến việc hệ thống bị “chết đứng” do mọi nỗ lực gởi gói tin của tất cả các trạm đều bị đụng độ. Slotted ALOHA trở nên quan trọng với lý do không mấy rành mạch lắm. Nó ra đời vào những năm 1970, được sử dụng trong một số hệ thống thí nghiệm thời đó, và rồi hầu như bị lãng quên. Và khi công nghệ truy cập Internet không qua cable được phát minh, đột nhiên lại phát sinh vấn đề làm sao để cấp phát đường truyền được chia sẻ cho nhiều người dùng cạnh tranh, Slotted ALOHA lại được lôi ra từ thùng rác để cứu rỗi cuộc đời. Vẫn thường có chuyện là các giao thức hợp lý một cách hoàn hảo lại không được sử dụng vì những lý do về chính trị, nhưng nhiều năm sau đó, một số người thông thái lại nhận ra rằng những giao thức bỏ đi từ lâu rồi đó lại có thể giúp họ giải quyết được vấn đề. Với lý do như vậy, trong chương này, chúng ta sẽ nghiên cứu một số giao thức ưu hạng hiện tại không được sử dụng rộng rãi lắm nhưng biết đâu có thể được sử dụng dễ dàng trong các ứng dụng ở tương lai. Dĩ nhiên là chúng ta cũng sẽ nghiên cứu nhiều giao thức đang được sử dụng rộng rãi hiện nay. 5.3.2.2 CSMA – Carrier Sense Multiple Access Giao thức ALOHA mặc dù đã chạy được, nhưng một điều đáng ngạc nhiên là người ta lại để cho các trạm làm việc tự do gởi thông tin lên đường truyền mà chẳng cần quan tâm đến việc tìm hiểu xem những trạm khác đang làm gì. Và điều đó dẫn đến rất nhiều vụ đụng độ tín hiệu. Tuy nhiên, trong mạng LAN, người ta có thể thiết kế các trạm làm việc sao cho chúng có thể điều tra xem các trạm khác đang làm gì và tự điều chỉnh hành vi của mình một cách tương ứng. Làm như vậy sẽ giúp cho hiệu năng mạng đạt được cao hơn. CSMA là một giao thức như vậy! Các giao thức mà trong đó các trạm làm việc lắng nghe đường truyền trước khi đưa ra quyết định mình phải làm gì tương ứng với trạng thái đường truyền đó được gọi là các giao thức có “cảm nhận” đường truyền (carrier sense protocol). Cách thức hoạt động của CSMA như sau: lắng nghe Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 69
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 kênh truyền, nếu thấy kênh truyền rỗi thì bắt đầu truyền khung, nếu thấy đường truyền bận thì trì hoãn lại việc gởi khung. Thế nhưng trì hoãn việc gởi khung cho đến khi nào? Có ba giải pháp: Theo dõi không kiên trì (Non-persistent CSMA): Nếu đường truyền bận, đợi trong một khoảng thời gian ngẫu nhiên rồi tiếp tục nghe lại đường truyền. Theo dõi kiên trì (persistent CSMA): Nếu đường truyền bận, tiếp tục nghe đến khi đường truyền rỗi rồi thì truyền gói tin với xác suất bằng 1. Theo dõi kiên trì với xác suất p (P-persistent CSMA): Nếu đường truyền bận, tiếp tục nghe đến khi đường truyền rỗi rồi thì truyền gói tin với xác suất bằng p. Dễ thấy rằng giao thức CSMA cho dù là theo dõi đường truyền kiên trì hay không kiên trì thì khả năng tránh đụng độ vẫn tốt hơn là ALOHA. Tuy thế, đụng độ vẫn có thể xảy ra trong CSMA! Tình huống phát sinh như sau: khi một trạm vừa phát xong thì một trạm khác cũng phát sinh yêu cầu phát khung và bắt đầu nghe đường truyền. Nếu tín hiệu của trạm thứ nhất chưa đến trạm thứ hai, trạm thứ hai sẽ cho rằng đường truyền đang rảnh và bắt đầu phát khung. Như vậy đụng độ sẽ xảy ra. H5.9 Mô tả không gian và thời gian diễn ra đụng độ Hậu quả của đụng độ là: khung bị mất và toàn bộ thời gian từ lúc đụng độ xảy ra cho đến khi phát xong khung là lãng phí! Bây giờ phát sinh vấn đề mới: các trạm có quan tâm theo dõi xem có đụng độ xảy ra không và khi đụng độ xảy ra thì các trạm sẽ làm gi? 5.3.2.2.1 CSMA với cơ chế theo dõi đụng độ (CSMA/CD – CSMA with Collision Detection) CSMA/CD về cơ bản là giống như CSMA: lắng nghe trước khi truyền. Tuy nhiên CSMA/CD có hai cải tiến quan trọng là: phát hiện đụng độ và làm lại sau đụng độ. Phát hiện đụng độ: Trạm vừa truyền vừa tiếp tục dò xét đường truyền. Ngay sau khi đụng độ được phát hiện thì trạm ngưng truyền, phát thêm một dãy nhồi (dãy nhồi này có tác dụng làm tăng cường thêm sự va chạm tín hiệu, giúp cho tất cả các trạm khác trong mạng thấy được sự đụng độ), và bắt đầu làm lại sau đụng độ. CSMA/CD, cũng giống như các giao thức trong LAN khác, sử dụng mô hình quan niệm như trong hình sau: Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 70
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 H5.10 CSMA/CD có thể ở một trong ba trạng thái: tranh chấp, truyền, rảnh Tại thời điểm t0, một trạm đã phát xong khung của nó. Bất kỳ trạm nào khác có khung cần truyền bây giờ có thể cố truyền thử. Nếu hai hoặc nhiều hơn các trạm làm như vậy cùng một lúc thì sẽ xảy ra đụng độ. Đụng độ có thể được phát hiện bằng cách theo dõi năng lượng hay độ rộng của xung của tín hiệu nhận được và đem so sánh với độ rộng của xung vừa truyền đi. Bây giờ ta đặt ra câu hỏi: Sau khi truyền xong khung (hết giai đoạn truyền), trạm sẽ bỏ ra thời gian tối đa là bao lâu để biết được là khung của nó đã bị đụng độ hoặc nó đã truyền thành công? Gọi thời gian này là “cửa sổ va chạm” và ký hiệu nó là Tw. Phân tích sau đây sẽ cho ra câu trả lời. Hình sau sẽ mô phỏng chi tiết về thời gian phát khung giữa hai trạm A và B ở hai đầu mút xa nhất trên đường truyền tải. H5.11 Thời gian cần thiết để truyền một khung Đặt Tprop là thời gian lan truyền tín hiệu giữa hai đầu mút xa nhau nhất trên đường truyền tải. Tại thời điểm t, A bắt đầu phát đi khung dữ liệu của nó. Tại t+Tprop-ε, B phát hiện kênh truyền rảnh và phát đi khung dữ liệu của nó. Tại t+ Tprop, B phát hiện sự đụng độ. Tại t+2Tprop-ε, A phát hiện sự đụng độ. Theo phân tích trên, thì Tw = 2Tprop Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 71
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 H5.12 Phát hiện đụng độ khi truyền tin Việc hủy bỏ truyền khung ngay khi phát hiện có đụng độ giúp tiết kiệm thời gian và băng thông, vì nếu cứ tiếp tục truyền khung đi nữa, khung đó vẫn hư và vẫn phải bị hủy bỏ. H5.13 Xử lý khu đụng độ Làm lại sau khi đụng độ: Sau khi bị đụng độ, trạm sẽ chạy một thuật toán gọi là back-off dùng để tính toán lại lượng thời gian nó phải chờ trước khi gởi lại khung. Lượng thời gian này phải là ngẫu nhiên để các trạm sau khi quay lại không bị đụng độ với nhau nữa. Thuật toán back-off hoạt động như sau: Rút ngẫu nhiên ra một con số nguyên M thõa: 0≤ M ≤ 2k . Trong đó k= min(n,10) , với n là tổng số lần đụng độ mà trạm đã gánh chịu. Kỳ hạn mà trạm phải chờ trước khi thử lại một lần truyền mới là M*Tw. Khi mà n đạt đến giá trị 16 thì hủy bỏ việc truyền khung. (Trạm đã chịu đựng quá nhiều vụ đụng độ rồi, và không thể chịu đựng hơn được nữa!) Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 72
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 ĐÁNH GIÁ HIỆU SUẤT CỦA GIAO THỨC CSMA/CD: Gọi: P là kích thước của khung, ví dụ như 1000 bits. C là dung lượng của đường truyền, ví dụ như 10 Mbps. Ta có thời gian phát hết một khung thông tin là P/C giây. Trung bình, chúng ta sẽ thử e lần trước khi truyền thành công một khung. Vì vậy, với mỗi lần phát thành công một khung (tốn P/C giây), ta đã mất tổng cộng 2eTprop (≈5Tprop) vì đụng độ. Thành thử hiệu năng của giao thức (tỉ lệ giữa thời gian hoạt động hữu ích trên tổng thời gian hoạt động) là: P 11 TCprop C == a= P 5Tprop , với C +51Taprop 1+ P +5P C Giá trị của a đóng vai trò rất quan trọng đến hiệu suất hoạt động của mạng kiểu CSMA/CD. 5.3.3 Phương pháp phân lượt truy cập đường truyền Bây giờ thử nhìn lại hai phương pháp điều khiển truy cập đường truyền “chia kênh” và “truy cập ngẫu nhiên”, ta sẽ thấy chúng đều có những điểm hay và hạn chế: Trong các giao thức dạng chia kênh, kênh truyền được phân chia một cách hiệu quả và công bằng khi tải trọng đường truyền là lớn. Tuy nhiên chúng không hiệu quả khi tải trọng của đường truyền là nhỏ: có độ trì hoãn khi truy cập kênh truyền, chỉ 1/N băng thông được cấp cho người dùng ngay cả khi chỉ có duy nhất người dùng đó hiện diện trong hệ thống. Các giao thức dạng truy cập ngẫu nhiên thì lại hoạt động hiệu quả khi tải trọng của đường truyền thấp. Nhưng khi tải trọng đường truyền cao thì phải tốn nhiều chi phí cho việc xử lý đụng độ. Các giao thức dạng “phân lượt” sẽ để ý đến việc tận dụng những mặt mạnh của hai dạng nói trên. Ý tưởng chính của các giao thức dạng “phân lượt” là không để cho đụng độ xảy ra bằng cách cho các trạm truy cập đường truyền một cách tuần tự. Về cơ bản, có hai cách thức để “phân lượt” sử dụng đường truyền: Thăm dò (polling): Trạm chủ (master) sẽ mời các trạm tớ (slave) truyền khi đến lượt. Lượt truyền được cấp phát cho trạm tớ có thể bằng cách: trạm chủ dành phần cho trạm tớ hoặc trạm tớ yêu cầu và được trạm chủ đáp ứng. Tuy nhiên có thể thấy những vấn đề sẽ gặp phải của giải pháp này là: chi phí cho việc thăm dò, độ trễ do phải chờ được phân lượt truyền, hệ thống rối loạn khi trạm chủ gặp sự cố. Chuyền thẻ bài (token passing): Thẻ bài điều khiển sẽ được chuyển lần lượt từ trạm này qua trạm kia. Trạm nào có trong tay thẻ bài sẽ được quyền truyền, truyền xong phải chuyền thẻ bài qua trạm kế tiếp. Những vấn đề cần phải quan tâm: chi phí quản lý thẻ bài, độ trễ khi phải chờ thẻ bài, khó khăn khi thẻ bài bị mất. 5.3.3.1 Ví dụ về phương pháp thăm dò: Thăm dò phân tán (Distributed Polling) Thời gian được chia thành những “khe” (slot). Giả sử hệ thống hiện có N trạm làm việc. Một chu kỳ hoạt động của hệ thống bắt đầu bằng N khe thời gian ngắn dùng để đặt chỗ (reservation slot). Khe thời gian dùng để đặt chỗ bằng với thời gian lan truyền tín hiệu giữa hai đầu mút xa nhất trên đường truyền. Tới khe đặt chỗ thứ i, trạm thứ i nếu muốn truyền dữ liệu sẽ phát tín hiệu đặt chỗ của mình lên kênh truyền, và tín hiệu này sẽ được nhìn thấy bởi tất cả các trạm khác trong mạng. Sau thời gian đặt chỗ, các trạm bắt đầu việc truyền dữ liệu của mình theo đúng trình tự đã đăng ký. Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 73
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 H5.14 Mô tả các chu kỳ hoạt động của hệ thống Thăm dò phân tán 5.3.3.2 Ví dụ về phương pháp chuyển thẻ bài: Token Ring Giao thức này sử dụng mạng kiểu hình vòng, dùng thẻ bài để cấp quyền sử dụng đường truyền. Mạng token ring bao gồm một tập hợp các trạm được nối với nhau thành một vòng. H5.15 Mô hình hoạt động của mạng Token Ring Dữ liệu luôn chạy theo một hướng vòng quanh vòng. Mỗi trạm nhận khung từ trạm phía trên của nó và rồi chuyển khung đến trạm phía dưới. Thẻ bài là công cụ để quyết định ai có quyền truyền tại một thời điểm. Cách thức hoạt động của mạng token ring như sau: một thẻ bài, thực chất chỉ là một dãy bit, sẽ chạy vòng quanh vòng; mỗi nút sẽ nhận thẻ bài rồi lại chuyển tiếp thẻ bài này đi. Khi một trạm có khung cần truyền và đúng lúc nó thấy có thẻ bài tới, nó liền lấy thẻ bài này ra khỏi vòng (nghĩa là không có chuyển tiếp chuỗi bit đặc biệt này lên vòng nữa), và thay vào đó, nó sẽ truyền khung dữ liệu của mình đi. Khi khung dữ liệu đi một vòng và quay lại, trạm phát sẽ rút khung của mình ra và chèn lại thẻ bài vào vòng. Hoạt động cứ xoay vòng như thế. Card mạng dùng cho token ring sẽ có trên đó một bộ nhận, một bộ phát và một bộ đệm dùng chứa dữ liệu. Khi không có trạm nào trong vòng có dữ liệu để truyền, thẻ bài sẽ lưu chuyển vòng quanh. Nếu một trạm có dữ liệu cần truyền và có thẻ bài, nó có quyền truyền một hoặc nhiều khung dữ liệu tùy theo qui định của hệ thống. Mỗi khung dữ liệu được phát đi sẽ có một phần thông tin chứa địa chỉ đích của trạm bên nhận; ngoài ra nó còn có thể chứa địa chỉ muticast hoặc broadcast tùy theo việc bên gởi muốn gởi khung cho một nhóm người nhận hay tất cả mọi người trong vòng. Khi khung thông tin chạy qua mỗi trạm trong vòng, trạm này sẽ nhìn vào địa chỉ đích trong khung đó để biết xem có phải nó là đích đến của khung không. Nếu phải, trạm sẽ chép nội dung của khung vào trong bộ đệm của nó, chỉ chép thôi chứ không được xóa khung ra khỏi vòng. Một vấn đề cần phải quan tâm đến là một trạm đang giữ thẻ bài thì nó có quyền truyền bao nhiêu dữ liệu, hay nói cách khác là trạm được cho bao nhiêu thời gian để truyền dữ liệu? Chúng ta gọi thời gian này là thời gian giữ thẻ bài – THT (Token Holding Time). Trong trường hợp trong vòng chỉ có một trạm cần truyền dữ liệu và các trạm khác không có nhu cầu truyền, thì ta có thể cấp THT cho trạm có nhu cầu càng lâu càng tốt. Điều này sẽ làm tăng hiệu suất sử dụng hệ thống một cách đáng kể. Bởi vì sẽ thật là ngớ ngẩn nếu bắt trạm ngừng, chờ thẻ bài chạy hết một vòng, rồi lại Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 74
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 truyền tiếp. Tuy nhiên, giải pháp trên sẽ không hoạt động tốt nếu có nhiều trạm trong vòng cần gởi dữ liệu. THT dài chỉ thích hợp cho những trạm cần truyền nhiều dữ liệu, nhưng lại không phù hợp với những trạm chỉ có ít thông điệp cần gởi đi ngay cả khi thông điệp này là tối quan trọng. Điều này cũng giống như tình huống mà bạn xếp hàng để sử dụng máy ATM ngay sau một anh chàng định rút ra 10 triệu đồng, trong khi bạn chỉ cần vào đấy để kiểm tra tài khoản của mình còn bao nhiêu tiền! Trong các mạng 802.5, THT mặc định là 10 ms. Từ thời gian giữ thẻ bài, chúng ta lại nghĩ ra một số đo quan trọng khác: Thời gian xoay vòng của thẻ bài – TRT (Token rotation time), nghĩa là lượng thời gian bỏ ra để thẻ bài đi hết đúng một vòng. Dễ nhận thấy rằng: TRT ≤ Số nút hoạt động × THT + Độ trễ của vòng Với “Độ trễ của vòng” là tổng thời gian để thẻ bài đi hết một vòng khi trong vòng không có trạm nào cần truyền dữ liệu, “Số nút hoạt động” ám chỉ số trạm có dữ liệu cần truyền. Giao thức 802.5 cung cấp một phương thức truyền dữ liệu tin cậy bằng cách sử dụng hai bit A và C ở đuôi của khung dữ liệu. Hai bit bày ban đầu nhận giá trị 0. Khi một trạm nhận ra nó là đích đến của một khung dữ liệu, nó sẽ đặt bit A trong khung này lên. Khi trạm chép khung vào trong bộ nhớ đệm của nó, nó sẽ đặt bit C lên. Khi trạm gởi thấy khung của nó quay lại với bit A vẫn là 0, nó biết là trạm đích bị hư hỏng hoặc không có mặt. Nếu bit A là 1, nhưng bit C là 0, điều này ám chỉ trạm đích có mặt nhưng vì lý do nào đó trạm đích không thể nhận khung (ví dụ như thiếu bộ đệm chẳng hạn). Vì thế khung này có thể sẽ được truyền lại sau đó với hy vọng là trạm đích có thể tiếp nhận nó. Chi tiết cuối cùng cần phải xem xét là: chính xác khi nào thì trạm sẽ nhả thẻ bài ra? Có hai đề nghị: a) nhả thẻ bài ra ngay sau khi trạm vừa truyền khung xong (RAT); b) nhả thẻ bài ra ngay sau khi trạm nhận lại khung vừa phát ra (RAR). H5.16 Nhả token: a)RAT b)RAR Quản lý hoạt động của mạng Token Ring Cần thiết phải đề cử ra một trạm làm nhiệm vụ quản lý mạng token ring gọi là monitor. Công việc của monitor là đảm bảo sức khỏe cho toàn bộ vòng. Bất kỳ trạm nào cũng có thể trở thành monitor. Thủ tục bầu chọn monitor diễn ra khi vòng vừa được tạo ra hoặc khi monitor của vòng bị sự cố. Một monitor mạnh khỏe sẽ định kỳ thông báo sự hiện diện của nó cho toàn vòng biết bằng một thông điệp đặc biệt. Nếu một trạm không nhận được thông báo hiện diện của monitor trong một khoảng thời gian nào đó, nó sẽ coi như monitor bị hỏng và sẽ cố trở thành monitor mới. Khi một trạm quyết định rằng cần phải có một monitor mới, nó sẽ gởi một thông điệp thỉnh cầu, thông báo ý định trở thành monitor của mình. Nếu thông điệp này chạy một vòng và về lại được trạm, trạm sẽ cho rằng mọi người đồng ý vị trí monitor của nó. Còn nếu đồng thời có nhiều trạm cùng gởi thông điệp thỉnh cầu, chúng sẽ phải áp dụng một luật lựa chọn nào đó, chẳng hạn như “ai có địa chỉ cao nhất sẽ thắng cử”. Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 75
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 Nhiệm vụ đáng chú ý của monitor là phải đảm bảo rằng luôn luôn có sự hiện diện của thẻ bài ở đâu đó trên vòng, có thể là đang di chuyển hay đang bị giữ bởi một trạm nào đó. Rõ ràng là thẻ bài có thể bị biến mất vì lý do nào đó chẳng hạn như lỗi bit, trạm đang giữ nó bị hư hỏng. Để phát hiện ra việc thẻ bài bị mất, khi thẻ bài chạy ngang qua monitor, nó sẽ bật một bộ đếm thời gian để tính giờ. Bộ đếm này có giá trị tối đa là: Số lượng trạm × THT + Độ trễ của vòng Trong đó “Số lượng trạm” là số các trạm làm việc đang hiện diện trên vòng, “độ trễ của vòng” là tổng thời gian lan truyền tín hiệu trên vòng. Nếu bộ đếm đạt đến giá trị tối đa mà monitor vẫn không thấy thẻ bài chạy qua nó nữa thì nó sẽ tạo ra thẻ bài mới. Monitor cũng phải kiểm tra xem có khung nào bị hỏng hoặc vô thừa nhận hay không. Một khung nếu có lỗi checksum hoặc khuôn dạng không hợp lệ sẽ chạy một cách vô định trên vòng. Monitor sẽ thu khung này lại trước khi chèn lại thẻ bài vào vòng. Một khung vô thừa nhận là khung mà đã được chèn thành công vào vòng, nhưng cha của nó bị chết, nghĩa là trạm gởi nó chỉ gởi nó lên vòng, nhưng chưa kịp thu nó lại thì đã bị chết (down). Những khung như vậy sẽ bị phát hiện bằng cách thêm vào một bit điều khiển gọi là monitor bit. Khi được phát lần đầu tiên, monitor bit trên khung sẽ nhận giá trị 0. Khi khung đi ngang qua monitor, monitor sẽ đặt monitor bit lên 1. Nếu monitor thấy khung này lại chạy qua nó với monitor bit là 1, nó sẽ rút khung này ra khỏi vòng. Một chức năng quản lý vòng khác là phát hiện ra một trạm bị chết. Nếu một trạm trong vòng bị chết, nó sẽ làm đứt vòng. Để tránh tình trạng này người ta thêm vào trạm một rờ-le điện tử (relay). Khi trạm còn mạnh khỏe, rờ-le sẽ mở và trạm được nối với vành, khi trạm bị chết và ngưng không cung cấp năng lượng cho rờ-le, rờ-le sẽ tự động đóng mạch và bỏ qua trạm này. H5.17 Sử dụng relay để tránh đứt vòng Khi monitor nghi ngờ một trạm bị chết, nó sẽ gởi đến trạm đó một khung đặc biệt gọi là khung beacon. Nếu không nhận được trả lời thích đáng, monitor sẽ coi trạm đó đã chết. ĐÁNH GIÁ VỀ MẠNG TOKEN RING: Ta sẽ khảo sát hai kiểu chuyển thẻ bài: Release After Reception (RAR) và Release After Transmisions (RAT). RAR: Nhả thẻ bài sau khi nhận lại dữ liệu Sau khi một trạm phát đi khung dữ liệu của nó, trạm sẽ chờ đến khi khung này quay trở lại mới chuyền thẻ bài cho trạm kế tiếp. Mạng IEEE 802.5 Token Ring (16Mbps) sử dụng cơ chế này. Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 76
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 H5.18 Mô phỏng cơ chế chuyền thẻ bài trong RAR Ta gọi hiệu suất truyền khung là η . Mạng kiểu RAR sẽ đạt được hiệu suất tối đa nếu một trạm RAR phát liên tục. Đặt: Tprop là thời gian lan truyền tín hiệu giữa hai đầu mút xa nhau nhất trên đường truyền tải. Ttran là thời gian để phát hết một khung dữ liệu lên đường truyền. P là kích thước của khung dữ liệu, ví dụ 1000 bits. C là dung lượng của đường truyền, ví dụ 10 Mbps. P Có Ttran = C Sau đây là biểu đồ mô phỏng mối liên quan giữa thời gian phát khung và thời gian truyền tín hiệu: H5.19 Thời gian lan truyền và phát khung với RAR Có thể thấy: 1 ηRAR = 1+ a Với Tprop a = Ttran Trong trường hợp một trạm luôn phải nhường token ngay sau khi token đi hết một vòng và quay trở lại nó thì hiện trạng phân bổ thời gian được vẽ ra dưới đây: Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 77
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 H5.20 Các khoảng thời gian một trạm phải trải qua khi gởi dữ liệu và chuyền thẻ bài Giả sử token có kích thước quá nhỏ để coi như thời gian phát nó bằng không, mạng có N trạm làm việc và khoảng cách giữa các trạm là bằng nhau. Vì vậy, thời gian lan truyền tín hiệu từ một trạm đến một trạm liền kề nó là Tprop/N. Có thể nhận thấy thời gian để token chuyển từ một trạm sang một trạm kề nó là Tprop/N. Vì vậy: T 11 tran ηRAR ==≈ TTprop ⎛⎞N +1 prop 1+ a TTprop ++tran 1+⎜⎟ NN⎝⎠Ttran RAT: Nhả thẻ bài ngay sau khi truyền dữ liệu Với kỹ thuật RAT, trạm sẽ chuyền thẻ bài điều khiển cho trạm kế tiếp ngay sau khi nó vừa phát song khung dữ liệu. Ví dụ mạng FDDI (Fiber Distributed Data Interface - 100Mbps) sử dụng kỹ thuật này. H5.21 Mô phỏng kỹ thuật RAT Gọi hiệu suất truyền khung là ηRAT . Với kỹ thuật RAT, hiệu suất đạt tối đa khi một trạm liên tục truyền khung. Sau đây là biểu đồ thời gian mô phỏng: Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 78
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 H5.22 Thời gian phát và lan truyền khung Có thể thấy khi một trạm phát khung liên tục thì ηRAT =1 Tuy nhiên khi một trạm buộc phải nhả token ngay sau khi nó vừa phát dữ liệu xong, thì biểu đồ thời gian có khác: 1 2 3 N 1 Thời điểm 0 Tprop Thời điểm Tprop T T + tran tran N T Thời điểm 22T + prop tran N H5.23 Khi một trạm phải nhả token ngay sau khi nó vừa phát dữ liệu Ta tính lại hiệu suất như sau: T 11 η ==tran = RAT TTproptran 1 prop a Ttranprop + 1+ 1+ Tprop N N Với a = NTtran Ttran 5.3.3.3 Ví dụ về phương pháp chuyền thẻ bài: Token Bus A B C D H G F E H5.24 Sơ đồ mạng Token Bus Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 79
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 Kỹ thuật Token Bus về bản chất là sử dụng mạng hình bus. Tuy nhiên người ta muốn thiết lập một vòng ảo trên đó để nó hoạt động giống như Token Ring. Nguyên tắc hoạt động như sau: trạm có nhu cầu truyền dữ liệu thì sẽ tham gia vào vòng ảo, ngược lại thì sẽ nằm ngoài và chỉ nghe thôi! Giải thuật bổ sung một trạm vào vòng: Mỗi trạm trong vòng có trách nhiệm định kỳ tạo điều kiện cho các trạm khác tham gia vào vòng. Trước khi chuyển thẻ bài đi, trạm sẽ gởi thông báo “tìm trạm đứng sau” (có địa chỉ giữa nó và trạm đứng liền kề hiện tại). Nếu sau một thời gian xác định mà vẫn không có yêu cầu gia nhập nào, trạm sẽ chuyển thẻ bài đến trạm kế tiếp như thường lệ. Nếu có yêu cầu gia nhập vòng, thì trạm sẽ ghi nhận trạm mới yêu cầu là trạm kế tiếp của nó và sẽ chuyển thẻ bài tới trạm kế mới này. Giải thuật rút lui ra khỏi vòng: Khi muốn rút ra khỏi vòng, trạm sẽ chờ đến khi nó có token, sau đó sẽ gởi yêu cầu “nối trạm đứng sau” tới trạm đứng trước nó, yêu cầu trạm đứng trước nối trực tiếp với trạm đứng liền sau nó. Ngoài ra còn phải quan tâm đến tình trạng mất thẻ bài, các trạm thành viên trong vòng bị hư hỏng. 5.4 Chuẩn hóa mạng cục bộ Ngoài mô hình OSI dùng cho việc chuẩn hóa các mạng nói chung, việc chuẩn hóa mạng cục bộ cũng đã được thực hiện trong một khoảng thời gian dài. Do đặc trưng riêng, việc chuẩn hóa mạng cục bộ chỉ được thực hiện trên hai tầng thấp nhất, tương ứng với tầng vật lý và liên kết dữ liệu trong mô hình OSI. H5.25 Mô hình phân tầng của mạng cục bộ Trong LAN, tầng liên kết dữ liệu được chia làm hai tầng con: LLC (Logical Link Layer) và MAC. MAC quản lý việc truy cập đường truyền, trong khi LLC đảm bảo tính độc lập của việc quản lý các liên kết dữ liệu với đường truyền vật lý và phương pháp truy cập đường truyền MAC. IEEE (Institute of Electrical and Electronic Engineers) là tổ chức đi tiên phong trong lĩnh vực chuẩn hóa mạng cục bộ với dự án IEEE 802 nổi tiếng bắt đầu được triển khai từ năm 1980 và kết quả là hàng loạt chuẩn thuộc họ IEEE 802.x ra đời, tạo nền tảng quan trọng cho việc thiết kế và cài đặt mạng nội bộ trong thời gian qua. Vị trí của họ chuẩn này càng cao hơn khi ISO đã xem xét và tiếp nhận chúng thành chuẩn quốc tế mang tên 8802.x. Đến nay họ IEEE 802.x bao gồm các chuẩn sau: IEEE 802.1 : High Level Interface IEEE 802.2 : Logical Link Control (LLC) IEEE 802.3: CSMA/CD Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 80
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 IEEE 802.4: Token bus IEEE 802.5: Token ring IEEE 802.6: MAN IEEE 802.7: Broadband Technical Advisory Group IEEE 802.8: Fiber Technical Advisory Group IEEE 802.9: Intergrated Data and Voice Network IEEE 802.10: Standard for Interoperable LAN security IEEE 802.11: Wireless LAN IEEE 802.12: 100VG – AnyLAN H5.23 sẽ mô tả vị trí tương đối của các chuẩn trên khi so sánh với chuẩn OSI: H5.26 Quan hệ giữa các chuẩn IEEE và mô hình OSI IEEE 802.1 là chuẩn đặc tả kiến trúc mạng, nối kết giữa các mạng và việc quản trị mạng đối với mạng cục bộ. IEEE 802.2 là chuẩn đặc tả tầng LLC (dịch vụ, giao thức) của mạng cục bộ. Có 3 kiểu giao thức LLC chính được định nghĩa: LLC type 1: Là giao thức kiểu không liên kết, không báo nhận. LLC type 2: Là giao thức kiểu có liên kết. LLC type 3: Là giao thức dạng không liên kết, có báo nhận. Các giao thức này được xây dựng dựa theo phương thức cân bằng của giao thức HDLC và có các khuôn dạng dữ liệu và các chức năng tương tự, đặc biệt là trong trường hợp LLC-type 2. IEEE 802.3: Là chuẩn đặc tả một mạng cục bộ dựa trên mạng Ethernet nổi tiếng do Digital, Intel và Xerox hợp tác phát triển từ năm 1990. IEEE 802.3 bao gồm cả tầng vật lý và tầng con MAC với các đặc tả sau: o Đặc tả dịch vụ MAC. o Giao thức MAC. o Đặc tả vật lý độc lập với đường truyền. o Đặc tả vật lý phụ thuộc vào đường truyền. Phần cốt lõi của IEEE 802.3 là giao thức MAC dựa trên phương pháp CSMA/CD đã trình bày ở phần trước. IEEE 802.4 là chuẩn đặc tả mạng cục bộ với hình trạng bus sử dụng thẻ bài để điều khiển truy cập đường truyền. IEEE 802.4 cũng bao gồm cả tầng vật lý và tầng con MAC với các đặc tả sau: o Đặc tả dịch vụ MAC. o Giao thức MAC. o Đặc tả dịch vụ tầng vật lý. o Đặc tả thực thể tầng vật lý. o Đặt tả đường truyền. IEEE 802.5 là chuẩn đặc tả mạng cục bộ với hình trạng vòng sử dụng thẻ bài để điều khiển truy cập đường truyền. IEEE 802.5 cũng bao gồm cả tầng vật lý và tầng con MAC với các đặc tả sau: o Đặc tả dịch vụ MAC. Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 81
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 o Giao thức MAC. o Đặc tả thực thể tầng vật lý. o Đặc tả nối trạm. IEEE 802.6 là chuẩn đặc tả một mạng tốc độ cao nối kết nhiều LAN thuộc các khu vực khác nhau của một đô thị. Mạng này sử dụng cáp quang với hình trạng dạng bus kép (dual-bus), vì thế còn được gọi là DQDB (Distributed Queue Dual Bus). Lưu thông trên mỗi bus là một chiều và khi cả cặp bus cùng hoạt động sẽ tạo thành một cấu hình chịu lỗi. Phương pháp điều khiển truy cập dựa theo một giải thuật xếp hàng phân tán có tên là QPDS (Queued-Packet, Distributed-Switch). IEEE 802.9 là chuẩn đặc tả một mạng tích hợp dữ liệu và tiếng nói bao gồm 1 kênh dị bộ 10 Mbps cùng với 95 kênh 64 Kbps. Giải thông tổng cộng 16 Mpbs. Chuẩn này được thiết kế cho các môi trường có lưu lượng lưu thông lớn và cấp bách. IEEE 802.10 là chuẩn đặc tả về an toàn thông tin trong các mạng cục bộ có khả năng liên tác (interoperable). IEEE 802.11 là chuẩn đặc tả mạng LAN không dây (Wireless LAN). Xu hướng chọn phương pháp truy cập CSMA được khẳng định. IEEE 802.12 là chuẩn đặc tả mạng cục bộ dựa trên công nghệ được đề xuất bởi AT&T, IBM và HP, gọi là 100 VG – AnyLAN. Mạng này sử dụng hình trạng mạng hình sao và một phương pháp truy cập đường truyền có điều khiển tranh chấp. Khi có nhu cầu truyền dữ liệu, trạm sẽ gởi yêu cầu đến hub và trạm chỉ có thể truyền dữ liệu khi được hub cho phép. Chuẩn này nhằm cung cấp một mạng tốc độ cao (100 Mbps và có thể lớn hơn) có thể hoạt động trong các môi trường hỗn hợp Ethernet và Token Ring, bởi thế nó chấp nhận cả hai dạng khung. 100 VG – AnyLAN là đối thủ cạnh tranh đáng gờm của 100BASE-T (Fast Ethernet) nhờ một số tính năng trội hơn, chẳng hạn về khoảng cách đi cáp tối đa cho phép 5.5 Giới thiệu một số công nghệ mạng LAN 5.5.1 Ethernet (802.3) Ethernet đã dễ dàng trở thành công nghệ mạng LAN thành công nhất trong suốt 20 năm qua. Được phát triển vào giữa thập kỷ 1970s bởi các nhà nghiên cứu tại Xerox Palo Atlto Research Center (PARC), Ethernet là một ví dụ thực tiễn của loại mạng cục bộ sử dụng giao thức CSMA/CD. 5.5.2 Tổng quan Khởi thủy, một phân đoạn mạng của Ethernet (Ethernet segment) được cài đặt trên một sợi cable đồng trục dài tối đa 500 m. Các trạm nối vào Ethernet segment bằng cách “mắc dây” (tab) nối vào nó. Các điểm đấu nối phải cách nhau ít nhất 2,5 m. Transceiver, một thiết bị nhỏ được gắn trực tiếp vào điểm đấu nối, làm nhiệm vụ nghe ngóng khi đường truyền rỗi để đưa tín hiệu ra đó khi trạm phát tín hiệu. Transceiver cũng làm nhiệm vụ nhận tín hiệu đến. Đến lượt transceiver lại được nối đến card mạng Ethernet, được gắn trong máy trạm. Tất cả những chi tiết luận lý làm nên giao thức Ethernet được cài đặt trong card mạng này. Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 82
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 H5.27 Bức phác họa Ethernet của Bob Metcalfe, người sáng lập ra Ethernet (Xerox PARC - 1972) Và mô tả chi tiết transceiver + adaptor Các segment có thể được nối với nhau bởi các repeater. Một repeater là một thiết bị dùng để chuyển tiếp tín hiệu số. Tuy nhiên, không được có hơn 4 repeater được đặt giữa hai trạm, có nghĩa là một mạng Ethernet nguyên thủy chỉ kéo dài tối đa là 2500 m. Bất kỳ tín hiệu nào được phát ra Ethernet sẽ được truyền quảng bá ra toàn mạng, repeater có nhiệm vụ chuyển tín hiệu từ trong segment ra ngoài, và nhận tín hiệu từ ngoài phát quảng bá vào trong segment. H5.28 Ethernet Repeater Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 83
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 5.5.2.1 Khuôn dạng khung thông tin của Ethernet Bên gởi sẽ bao gói gói tin IP thành khung Ethernet như sau: H5.29 Khuôn dạng khung thông tin Ethernet Preamble: dài 7 bytes với mẫu 10101010 theo sau bởi 1 byte với mẫu 10101011, được sử dụng để đồng bộ hóa tốc độ đồng hồ giữa bên gởi và bên nhận. Source and dest. addresses: Địa chỉ nguồn và đích, gồm 6 bytes. Khung được nhận bởi tất cả các trạm trong LAN. Khung bị xóa nếu dest. address không trùng với địa chỉ MAC của bất kỳ trạm nào hoặc không phải thuộc dạng multicast. Type: chỉ ra giao thức được sử dụng ở tầng cao hơn, thường là IP, nhưng các giao thức khác vẫn được hỗ trợ - ví dụ: Novell IPX và AppleTalk. CRC: Phần kiểm tra lỗi. Lỗi được kiểm tra tại trạm đích. Nếu khung có lỗi, nó sẽ bị xóa. 5.5.2.2 Địa chỉ Ethernet Mỗi host trong một mạng Ethernet (thật ra là tất cả các host trên thế giới) có một địa chỉ Ethernet duy nhất. Mô tả một cách kỹ thuật, địa chỉ được gắn vào card mạng chứ không phải máy tính; nó được ghi vào ROM trên card mạng. Các địa chỉ Ethernet thường được in theo thể thức mà con người có thể đọc được: một dãy gồm 6 bytes được viết dưới dạng thập lục phân, cách nhau bởi dấu hai chấm. Ví dụ 8:0:2b:e4:b1:2 là cách biểu diễn dễ đọc của địa chỉ Ethernet sau 00001000 00000000 00101011 11100100 10110001 00000010 Để đảm bảo rằng mọi card mạng được gán một địa chỉ duy nhất, mỗi nhà sản xuất thiết bị Ethernet được cấp cho một phần đầu địa chỉ (prefix) khác nhau. Ví dụ Advanced Micro Devices đã được cấp phần đầu dài 24 bit x08002 (hay 8:0:2). Nhà sản xuất này sau đó phải đảm bảo phần đuôi (suffix) của các địa chỉ mà họ sản xuất ra là duy nhất. Mỗi khung được phát ra Ethernet sẽ được nhận bởi tất cả các card mạng có nối với đường truyền. Mỗi card mạng sẽ so sánh địa chỉ đích trong khung với địa chỉ của nó, và chỉ cho vào máy tính những khung nào trùng địa chỉ. Địa chỉ duy nhất như vậy gọi là địa chỉ unicast. Ngoài ra còn có loại địa chỉ broadcast là loại địa chỉ quảng bá, có tất cả các bit đều mang giá trị 1. Mọi card mạng đều cho phép các khung thông tin có địa chỉ đích là broadcast đi đến host của nó. Cũng có một loại địa chỉ khác gọi là multicast, trong đó chỉ một vài bit đầu được đặt là 1. Một host có thể lập trình điều khiển card mạng của nó chấp nhận một số lớp địa chỉ multicast. Địa chỉ multicast được dùng để gởi thông điệp đến một tập con (subset) các host trong mạng Ethernet. 5.5.2.3 Cách thức mã hóa tín hiệu Để chuyển đổi dữ liệu bit sang tín hiệu truyền trên đường truyền, Ethernet dùng kiểu mã hóa Manchester. Trong sơ đồ mã hóa Manchester, một bit sẽ được mã hóa bằng một sự thay đổi điện thế. Với bit “1”, điện thế đổi từ 1 xuống 0. Còn với bit “0”, điện thế đổi từ 0 lên 1. H5.30 Mã hóa Machester Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 84
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 5.5.2.4 Giải thuật truy cập đường truyền Ethernet sử dụng giải thuật CSMA/CS+Exponential backoff, được trình bày cụ thể như sau: Nhận một gói tin từ tầng cao hơn; K := 0; n :=0; // K: thời gian chờ đợi ngẫu nhiên; n: số vụ đụng độ đã gặp phải repeat: chờ trong khoảng thời gian K*512 bit-time; while (đường truyền bận) wait; chờ tiếp 96 bit-time sau khi nhận thấy không có tín hiệu trên đường truyền; truyền khung và chú ý phát hiện đụng độ; if (có đụng độ) { ngừng truyền và phát tiếp một dãy nhồi 48-bit; n ++; m:= min(n, 10); m chọn K ngẫu nhiên từ tập hợp {0, 1, 2, , 2 -1}. if (n < 16) goto repeat; else bỏ việc truyền; 5.5.2.5 } Các công nghệ Ethernet 5.5.2.5.1 10-BASE-2 Giải thích các ký hiệu: 10: 10 Mbps 2: chiều dài cable tối đa là 200 m Base: Baseband, Broad: Broadband. Mạng Ethernet 10BASE2 sử dụng cáp đồng trục gầy, hình thái bus. Trong trường hợp mạng có nhiều segments, các repeaters sẽ được sử dụng để nối kết các segments này lại. Hình 2.31 Mô hình mạng 10BASE2 Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 85
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 5.5.2.5.2 10-BASE-T và 100-BASE-T Mạng đạt tốc độ 10/100 Mbps, về sau được gọi là “fast Ethernet”. Chữ T viết tắt cho Twisted Pair: cáp xoắn đôi. Cách thức nối mạng được mô phỏng như sau: H5.32 Mô hình mạng 10BaseT Các HUB được nối tới các SWITCH bằng cáp xoắn đôi. Với cách thức đấu nối như vậy, mạng được gọi là “hình sao”. Cơ chế CSMA/CD được cài đặt tại HUB 5.5.2.5.3 GIGABIT ETHERNET Gbit Ethernet sử dụng khuôn dạng khung chuẩn của Ethernet. Nó cho phép mạng hoạt động trên cả hai kiểu nối kết điểm điểm và kênh quảng bá chia sẻ. Trong kiểu nối kết điểm-điểm, Gbit Ethernet sử dụng các switches thay cho các hub. Đường truyền được sử dụng theo kiểu hai chiều đồng thời với tốc độ 1 Gbps. Trong kiểu kênh quảng bá chia sẻ, Gbit Ethernet sử dụng các hubs làm kênh quảng bá và áp dụng giải thuật CSMA/CD để các trạm chia sẻ việc sử dụng các hubs này. 5.5.3 FDDI (Fiber Distributed Data Interface) Theo nhiều phương diện, FDDI tương tự như 802.5 và IBM Token Ring. Tuy nhiên, cũng có những khác biệt đáng kể, một số phát sinh vì lý do FDDI chạy trên cáp quang, một số khác phát sinh do có nhiều đổi mới sau khi người ta phát minh ra IBM Token Ring. Chúng ta sẽ thảo luận về những khác biệt quan trọng trong phần dưới đây. 5.5.3.1 Các tính chất vật lý Không giống như mạng 802.5, một mạng FDDI bao gồm một vòng đôi = hai vòng độc lập truyền dữ liệu theo hai chiều ngược nhau (xem H5.33.a). H5.33 Vòng quang đôi: a) hoạt động bình thường; b) vòng chính bị hỏng Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 86
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 Vòng phụ không được sử dụng trong khi hệ thống hoạt động bình thường, nó chỉ vào cuộc khi vòng chính bị sự cố (xem H5.33.b). Nghĩa là vòng chính sẽ quành lại vòng phụ để tạo ra một vòng hoàn chỉnh, và chính điều này giúp cho FDDI có khả năng chịu lỗi khi một cộng cáp bị đứt hay một trạm trong vòng bị hỏng. Do phải chịu phí tổn khi cấu hình theo kiểu vòng đôi, nên FDDI còn cho phép một trạm chọn nối vào chỉ một vòng đơn thôi. Những trạm như vậy gọi là những “trạm nối đơn” (single attachment station – SAS). Những trạm nối cả vào hai vòng dĩ nhiên sẽ được gọi là những “trạm đấu đôi” (dual attachment station – DAS). Một bộ tập trung (concentrator) sẽ được sử dụng để nối các SAS vào vòng đôi (xem H5.34) H5.34 Các SAS được nối vào bộ tập trung Nếu một SAS bị hỏng hóc, bộ tập trung sẽ phát hiện ra tình trạng này và sử dụng cơ chế bỏ qua tín hiệu quang (obtical bypass) để cô lập SAS bị hỏng, vì thế giữ cho vòng được thông suốt. Trong FDDI, bộ đệm của giao diện mạng có thể có kích thước khác nhau tại những trạm khác nhau, mặc dù kích thước của nó không bao giờ nhỏ hơn 9 bit và lớn hơn 80 bit. Một trạm cũng có thể bắt đầu phát các bit trong bộ đệm đi trước khi bộ đệm của nó bị đầy. Dĩ nhiên là tổng thời gian để một thẻ bài di chuyển hết một vòng là một hàm của kích thước của các bộ đệm này. Ví dụ, FDDI là mạng tốc độ 100 Mbps, nó có thời gian xử lý 1 bit là 10 ns. Nếu mỗi trạm cài đặt buffer dài 10 bit và chờ cho đến khi buffer bị đầy một nửa mới bắt đầu truyền, thì mỗi trạm tạo ra thời gian trì hoãn là 5 × 10 ns = 50 ns đối với tổng thời gian xoay vòng mạng. FDDI còn có các tính chất vật lý khác. Chẳng hạn, một mạng đơn có giới hạn chuẩn là có tối đa 500 trạm làm việc, với khoảng cách xa nhất giữa một cặp trạm bất kỳ là 2 km. Nhưng trên hết, mạng lại bị giới hạn với kích thước tổng cộng là 200 km cáp quang. Do tính chất là vòng đôi, nên tổng kích thước cáp quang nối tất cả các trạm là 100 km. Ngoài ra, mặc dù ký tự “F” ám chỉ cáp quang, nhưng chuẩn FDDI đã được định nghĩa để có thể chạy trên một số thiết bị tải khác, bao gồm cả cáp đồng trục và cáp xoắn đôi. Tuy nhiên cũng nên cẩn thận khi xét đến tổng kích thước mà vòng bao phủ. Như chúng ta sẽ thấy dưới đây, lượng thời gian bỏ ra để cho thẻ bài đi hết một vòng mạng sẽ đóng vai trò quan trọng trong giải thuật điều khiển truy cập. FDDI sử dụng phương pháp mã hóa 4B/5B. Do FDDI chuẩn mạng phổ biến đầu tiên sử dụng cáp quang, nên các con chíp mã hóa dạng 4B/5B chạy trên tốc độ của FDDI có rất nhiều ngoài thị trường. 5.5.3.2 Giải thuật “Thẻ bài được định thời” – Timed Token Các luật qui định thời gian giữ thẻ bài trong FDDI phức tạp hơn trong 802.5 một ít. THT cho mỗi trạm được tính như trong phần trình bày về Token Ring, và được tinh chỉnh để có được một giá trị hợp lý. Ngoài ra, để đảm bảo cho mỗi trạm có cơ hội truyền trong một khoảng thời gian cụ thể nào đó, nghĩa là để đặt một cận trên cho giá trị TRT mà mọi trạm đều thấy được, chúng ta định nghĩa thông số “đích thời gian xoay vòng của thẻ bài” (target token rotation time – TTRT). (Việc các trạm thống nhất với nhau về thời gian TTRT như thế nào sẽ được trình bày trong phần phía dưới). Mỗi trạm đo thời gian giữa hai lần liên tiếp thẻ bài đến nó, chúng ta gọi thời gian này là TRT đo được của trạm (measured TRT). Nếu thời gian TRT đo được của trạm lớn hơn thời gian TTRT được dàn xếp trước đó thì thẻ bài bị trễ, vì thế trạm sẽ không được truyền dữ liệu nữa. Ngược lại, thẻ bài đến sớm và trạm sẽ có quyền giữ thẻ bài trong khoảng thời gian (TTRT-TRT). Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 87
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 Tuy nhiên, có vấn đề phát sinh như sau: Nếu một nút có quá nhiều dữ liệu cần phải gởi có cơ hội giữ thẻ bài, nó sẽ tận dụng hết thời gian giữ thẻ bài được phép. Vì thế nút kế sau nó sẽ tính toán và thấy thời gian TTRT và TRT là bằng nhau, nghĩa là nút kế sau này sẽ không có quyền truyền dữ liệu nữa. Để tính đến khả năng này, FDDI định nghĩa hai lớp giao thông trên mạng: đồng bộ và dị bộ. Khi một trạm có được thẻ bài, nó luôn được phép gởi dữ liệu dạng đồng bộ mà không cần phải quan tâm là thẻ bài tới sớm hay trễ. Ngược lại, trạm có thể gởi dữ liệu dạng dị bộ chỉ khi thẻ bài tới sớm. Chú ý rằng các khái niệm đồng bộ và dị bộ ở đây có thể gây hiểu lầm. Bằng cách dùng khái niệm đồng bộ, FDDI ám chỉ rằng giao thông trên mạng là có nhạy cảm với độ trễ thông tin. Ví dụ, người ta sẽ muốn gởi âm thanh hay video trên mạng FDDI theo kiểu đồng bộ. Ngược lại, những ứng dụng nào quan tâm đến thông lượng của đường truyền thì sẽ thích kiểu truyền dị bộ hơn. Ví dụ, ứng dụng truyền file trên mạng sẽ muốn sử dụng kiểu lưu thông dị bộ trên FDDI. Lại thêm vấn đề phát sinh: Do kiểu lưu thông dạng đồng bộ không có quan tâm đến việc thẻ bài đến sớm hay muộn, nên có khả năng nếu trạm co-dãn thời gian gởi dữ liệu đồng bộ thì thông số TTRT không còn ý nghĩa gì nữa! Để giải quyết vấn đề này, ta qui định: tổng thời gian gởi dữ liệu đồng bộ trong một vòng xoay của thẻ bài không được vượt quá TTRT. 5.5.3.3 Quản lý thẻ bài Các cơ chế mà FDDI dùng để đảm bảo luôn có một thẻ bài hợp lệ chạy trên vòng cũng khác so với 802.5, do chúng dính với quá trình thiết đặt TTRT. Trước tiên, tất cả các trạm trong vòng luôn quan sát để đảm bảo là thẻ bài không bị mất. Để ý rằng một trạm trên vòng luôn có thể thấy được thời gian truyền hợp lệ của khung hay là thẻ bài. Thời gian rỗi tối đa giữa những lần truyền hợp lệ mà mỗi trạm nên biết qua là bằng độ trễ của vòng cộng với thời gian bỏ ra để truyền một khung đầy. (Trên một vòng có kích thước tối đa, thời gian tối đa để truyền một khung đầy là nhỏ hơn 2.5 ms). Do đó, mỗi trạm sẽ đặt bộ đếm lên, bộ đếm này sẽ hết hạn trong thời gian 2.5 ms. Nếu bộ đếm hết hạn, trạm sẽ nghi ngờ là có vấn đề không ổn và sẽ phát khung “thỉnh cầu”. Ngược lại khi bộ đếm chưa hết hạn mà trạm thấy được một sự truyền hợp lệ, nó sẽ đặt lại giá trị tối đa của bộ đếm là 2.5 ms. Khung thỉnh cầu trong FDDI khác với trong 802.5 do nó có chứa giá trị TTRT mà trạm mời chào (bid for the TTRT), nghĩa là: đó là thời gian xoay vòng của thẻ bài mà trạm cảm thấy đủ để các ứng dụng chạy trên nó thỏa mãn các ràng buộc về thời gian. Một trạm có thể gởi khung thỉnh cầu trong khi không có thẻ bài trong tay, và nó thường làm vậy khi có nghi ngờ mất thẻ bài hoặc khi mới tham gia vào vòng lần đầu tiên. Nếu khung thỉnh cầu đi được hết một vòng và quay lại, trạm phát sẽ xóa nó đi và hiểu rằng giá trị TTRT được mời chào trong đó là giá trị nhỏ nhất. Bây giờ có thể coi là trạm đang nắm thẻ bài, nghĩa là nó có trách nhiệm chèn vào mạng một thẻ bài hợp lệ, và có thể tiếp tục với giải thuật dùng thẻ bài thông thường. Khi một nút nhận được một khung thỉnh cầu, nó kiểm tra xem giá trị TTRT được mời chào trong đó có nhỏ hơn giá trị TTRT của chính nó không. Nếu nhỏ hơn, nó sẽ đặt lại giá trị TTRT của nó thành giá trị TTRT được mời chào. Nếu lớn hơn, trạm sẽ xóa khung thỉnh cầu này đi, chèn vào vòng một khung thỉnh cầu mới chứa giá trị TTRT được mời chào bằng giá trị TTRT của nó. Trường hợp cuối cùng, nếu giá trị TTRT được mời chào bằng với giá trị TTRT của trạm, trạm sẽ so sánh địa chỉ của trạm gởi khung thỉnh cầu và địa chỉ của nó, địa chỉ nào lớn hơn sẽ thắng – nghĩa là bên thắng sẽ sở hữu khung thỉnh cầu. Do đó, nếu một khung thỉnh cầu đi hết một vòng và trở về trạm gởi, trạm gởi sẽ biết rằng nó là người mời chào giá trị TTRT duy nhất và nó có thể tạo ra một thẻ bài mới một cách an toàn. Tại thời điểm đó, tất cả các trạm bấy giờ đều đồng ý rằng giá trị TTRT là giá trị đủ nhỏ để làm cho tất cả chúng cảm thấy hạnh phúc! 5.5.4 Khuôn dạng của khung thông tin 8848 48 32 824 Start of Dest Src End of Control Body CRC Status frame addr addr frame H5.35 Khung thông tin FDDI Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 88
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 Do FDDI sử dụng cơ chế mã hóa 4B/5B, nên nó dùng các ký tự điều khiển 4B/5B. Ngoài ra trong phần Control có tồn tại một bit để phân biệt kiểu lưu thông là dị bộ hay đồng bộ. 5.5.5 Mạng không dây (802.11) Mạng không dây là kỹ thuật nối mạng đang phát triển nhanh hiện nay. Như chúng ta đã biết, khả năng để xây dựng mạng không dây là hầu như không có giới hạn, trải dài từ cách sử dụng tín hiệu hồng ngoại để dựng mạng nội bộ trong phạm vi một tòa nhà cho đến việc kiến thiết mạng toàn cầu từ một lưới các vệ tinh quĩ đạo thấp. Phần này sẽ có cái nhìn gần hơn vào một kỹ thuật cụ thể xoay quanh chuẩn 802.11 đang nổi hiện nay. Giống như những người anh em Ethernet và Token Ring, 802.11 được thiết kế để hoạt động trong một phạm vi địa lý hẹp (các ngôi nhà, các tòa nhà văn phòng, các khu đại học) và thách thức quan trọng nó đặt ra là phải trù tính đến việc truy xuất đến phương tiện truyền thông chia sẻ - trong trường hợp này là các tín hiệu lan truyền trong không gian. 802.11 hỗ trợ thêm một số tính năng như các dịch vụ có giới hạn về thời gian, quản lý năng lượng và các cơ chế an toàn, nhưng chúng ta chỉ tập trung vào thảo luận về chức năng cơ bản của nó thôi. 5.5.5.1 Các tính chất vật lý 802.11 được thiết kế để chạy trên ba phương tiện vật lý khác nhau - hai dựa trên sóng radio phổ rộng và một dựa trên tia hồng ngoại được khuếch tán. Phiên bản chạy trên sóng radio hiện đang chạy với tốc độ 11 Mbps, nhưng có thể sớm đạt được tốc độ 54 Mbps. Ý tưởng đằng sau khái niệm phổ tần rộng là nhằm trải rộng tín hiệu lên trên một băng tần rộng hơn so với bình thường, vì thế có thể giảm thiểu tác động của sự giao thoa tín hiệu với các thiết bị khác. Ví dụ, kỹ thuật “nhảy tần số” (frequency hopping) là một kỹ thuật sử dụng phổ tần rộng, nó xoay quanh việc gởi tín hiệu qua một dãy tần số ngẫu nhiên; nghĩa là lần đầu sẽ gởi trên một tần số, lần hai gởi trên tần số khác, lần thứ ba và vân vân. Dãy tần số này không thật sự là ngẫu nhiên mà được tính toán một cách có giải thuật bởi một bộ sinh số ngẫu nhiên. Bên nhận sẽ dùng cùng một giải thuật như bên gởi và do đó có thể nhảy qua các tần số khác nhau đồng bộ với bên gởi để nhận chính xác khung thông tin. Một kỹ thuật sử dụng phổ tần rộng khác, được gọi là “dãy trực tiếp” (direct sequence), cũng đạt được cùng một hiệu quả bằng cách thể hiện một bit trong khung thành nhiều bit trong tín hiệu truyền đi. Với mỗi bit bên gởi muốn truyền đi, nó thực ra sẽ gởi một chuỗi bit là kết quả của phép toán exclusive-OR của bit đó với một chuỗi n bit ngẫu nhiên. Cũng như trong frequency hopping, chuỗi n bit này được sinh ra bởi một bộ sinh số ngẫu nhiên và được hiểu bởi cả hai bên gởi và nhận. Các giá trị được truyền đi, được gọi là “mã cắt lát” n bit (n-bit chipping code), sẽ rải tín hiệu trên một dãi tần rộng hơn gấp n lần so với dãi tần mà thông thường khung cần để được truyền đi. H5.35 là một ví dụ về mã cắt lát 4 bit. H5.36 Ví dụ về mã cắt lát 4 bit. 802.11 định nghĩa một lớp vật lý sử dụng cơ chế “nhảy tần số” (trên 79 dải tần có độ rộng 1-Mhz), lớp vật lý thứ hai sử dụng “dãy trực tiếp” (sử dụng dãy cắt lát 11 bit). Cả hai chuẩn đều chạy trên sóng điện từ băng tần 2.4 GHz. Trong cả hai trường hợp, việc trải rộng phổ truyền đều có điểm Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 89
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 thú vị là làm cho tín hiệu giống như nhiễu đối với bất kỳ bên nhận nào không biết chuỗi ngẫu nhiên giả. Chuẩn vật lý thứ ba của 802.11 dựa trên tín hiệu hồng ngoại. Tín hiệu lưu thông sẽ được khuếch tán, nghĩa là bên gởi và bên nhận không cần phải hướng vào nhau và không cần tầm nhìn rõ ràng. Kỹ thuật này có phạm vi hoạt động khoảng 10 m và bị giới hạn chỉ trong các tòa nhà mà thôi. 5.5.5.2 Tránh đụng độ (Collision Avoidance) Thoạt nhìn, có vẻ như giao thức không dây cũng tuân thủ cùng giải thuật như ở Ethernet: đợi cho đến khi đường truyền rỗi thì mới truyền, lùi lại nếu có đụng độ. 802.11 cũng làm tương tự như vậy. Tuy nhiên, vấn đề phức tạp hơn trong hệ thống mạng không dây, bởi vì không phải tất cả các nút đều có thể thấy nhau! ABCD H5.37 Ví dụ về mạng không dây Xét tình huống được chỉ ra trong H5.37, mỗi trạm chỉ có thể gởi và nhận tín hiệu đến hai nút kề trái và phải của nó. Ví dụ nút B có thể trao đổi các khung dữ liệu với nút A và C nhưng không thể phát tín hiệu đến D được, trong khi C chỉ có thể trao đổi với B và D mà không thể với A. (Tầm phủ sóng của A và D không được vẽ trong hình). Giả sử cả A và C cùng muốn nói giao tiếp với B và do đó chúng cùng gởi khung đến B. A và C không biết gì về nhau do sóng không thể đi xa như vậy. Hai khung này sẽ bị đụng độ tại B, nhưng không như trong Ethernet, không ai trong A và C hay biết gì về sự đụng độ này. A và C được gọi là các nút ẩn (hiden nodes) đối với nhau. Một vấn đề liên quan nữa, gọi là vấn đề “nút bị phơi trần” (exposed node problem), phát sinh trong tính huống sau: Giả sử B đang gởi cho A, nút C nhận biết được tình huống này vì nó nghe được việc truyền của B. Và sẽ là sai lầm nếu C kết luận là nó không thể truyền đến bất kỳ nút nào khác do nó nghe thấy B đang truyền. Ví dụ, giả sử C muốn truyền cho D thì việc này không gây ảnh hưởng gì vì việc truyền từ C đến D không can dự vào khả năng nhận tín hiệu của A từ B. (Chỉ gây ảnh hưởng khi A truyền cho B, nhưng trong trường hợp này B đang truyền). 802.11 giải quyết hai vấn đề trên bằng một giải thuật gọi là “Đa truy cập với cơ chế tránh đụng độ” – Multiple Access with Collision Avoidance (MACA). Ý tưởng là cho hai bên gởi và nhận trao đổi những khung điều khiển với nhau trước khi thật sự truyền dữ liệu. Việc trao đổi này dụng ý là để thông báo cho các trạm lân cận rằng một phiên truyền dữ liệu sắp xảy ra. Cụ thể giải thuật như sau: Bên gởi gởi một khung “yêu cầu gởi” – Request To Send (RTS) đến bên nhận; khung RTS có chứa một trường, trong đó chỉ ra bên gởi muốn giữ kênh truyền bao lâu ( nghĩa là nó chỉ ra chiều dài của khung cần gởi). Bên nhận sẽ trả lời bằng khung “sẵn sàng nhận” – Clear To Send (CTS); khung này sẽ lặp lại trường chiều dài khung như phía bên gởi. Bất kỳ trạm nào thấy khung CTS cũng hiểu được rằng trạm bên nhận ở gần nó, cho nên nó sẽ không thể gởi khung trong khoảng thời gian được chỉ ra trong CTS. Còn những trạm thấy khung RTS nhưng không thấy khung CTS đâu thì chắc chắn là không ở gần bên nhận, do đó chúng có quyền tự do gởi khung đi. Có thêm hai chi tiết nữa để hoàn thiện bức tranh về Wireless LAN. Thứ nhất, bên nhận gởi một khung báo nhận (ACK) cho bên gởi sau khi đã nhận thành công một khung dữ liệu. Tất cả các nút khác phải chờ khung ACK này đi qua trước khi thử truyền khung của mình. (Khung ACK này không có trong phiên bản MACA gốc, thay vào đó nó được đề nghị trong một phiên bản mở rộng được gọi là MACW: MACA for Wireless LANs). Thứ hai, trường hợp có hơn hai trạm phát hiện kênh truyền rỗi, chúng sẽ gởi khung RTS cùng lúc, dẫn đến các khung này bị va chạm với nhau. 802.11 không có hỗ trợ cơ chế phát hiện đụng độ, thay vào đó, các trạm nhận ra sự đụng độ khi Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 90
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 chúng không nhận được các khung CTS sau một khoảng thời gian nào đó. Nếu thế, mỗi trạm sẽ chờ đợi sau một khoảng thời gian ngẫu nhiên nào đó trước khi thử gởi khung RTS lần nữa. Khoảng thời gian mà một trạm chờ để thử lại được định nghĩa giống như thuật toán back-off trong Ethernet. 5.5.5.3 Hệ thống phân tán Như những gì đã trình bày, 802.11 có thể thích hợp với cấu hình mạng dạng ad-hoc, trong đó các nút có thể hoặc không thể giao tiếp với những nút còn lại, tùy thuộc vào khoảng cách giữa chúng là gần hay xa. Ngoài ra, do một trong những thuận lợi của mạng không dây là các nút có thể tự do di chuyển do chúng không bị trói buộc bởi hệ thống dây nối, tập các nút có thể thấy nhau trực tiếp là thay đổi theo thời gian. Để giúp giải quyết vấn đề di động và nối kết một phần này, 802.11 định nghĩa thêm một kiến trúc trên một tập các nút. Các nút có quyền tự do giao tiếp trực tiếp với nhau như đã trình bày, nhưng trong thực tế chúng hoạt động bên trong kiến trúc này. H5.38 Các điểm truy cập được nối kết vào mạng phân tán Thay vì tất cả các nút được tạo ra như nhau, một số nút được phép đi lang thang (đó là máy laptop của bạn) và một số được nối kết tới một hạ tầng mạng có nối dây. Các trạm nối kết có dây được gọi là các điểm truy cập - “access point” (AP) và chúng được nối với nhau bằng cái gọi là hệ thống phân tán. H5.38 mô phỏng một hệ thống phân tán nối kết ba điểm truy cập, mỗi điểm truy cập phục vụ các nút di động trong khu vực mình phụ trách. Mỗi khu vực này giống như một cell trong hệ thống điện thoại di động, với AP hoạt động giống như Base station. Mặc dù hai nút có thể giao tiếp trực tiếp với nhau nếu chúng ở trong tầm với của nhau, tuy nhiên ý tưởng ở trong kiến trúc này là: mỗi nút sẽ kết hợp với một điểm truy cập của nó. Ví dụ, để nút A giao tiếp được với nút E, đầu tiên A gởi khung của nó đến điểm truy cập AP-1, AP-1 sẽ gởi khung qua hệ thống phân tán đến AP-3, rồi AP-3 sẽ phân phát khung đến E. Chỉ ra AP-1 làm cách nào để chuyển khung đến AP-3 là nằm ngoài phạm vi của 802.11, một giao thức cầu nối (sẽ được nghiên cứu ở tầng mạng) có thể được sử dụng để làm nhiệm vụ này. Những gì 802.11 có thể làm là xác định cách thức các nút chọn ra AP của chúng, và thú vị hơn nữa là làm sao giao thức này hoạt động được trong tình cảnh các nút di chuyển từ cell này đến cell khác. Kỹ thuật để chọn ra một AP được gọi là kỹ thuật “quét” (scanning) và nó xoay quanh bốn bước sau: 1. Nút gởi một khung Probe (thăm dò). 2. Tất cả điểm truy cập (AP) trong tầm với của nút sẽ trả lời bằng một khung Probe Response (trả lời thăm dò). 3. Nút sẽ chọn một trong các điểm truy cập trên và gởi đến điểm truy cập đó một khung Association Request (yêu cầu gia nhập). 4. Điểm truy cập trả lời bằng một khung Association Reponse (trả lời cho yêu cầu gia nhập). Một nút tiến hành giao thức này khi nó lần đầu tham gia vào mạng hoặc nó không hài lòng với AP hiện tại. Điều này có thể xảy ra, ví dụ như vì tín hiệu từ AP hiện tại yếu dần do nút càng di chuyển xa AP. Mỗi khi nút kiếm được AP mới, AP mới sẽ nhắc nhở AP cũ về sự thay đổi này. Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 91
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 H5.39 Sự di động của nút mạng Lấy ví dụ như trong H5.38, khi mà nút C di chuyển từ cell được phục vụ bởi AP-1 sang cell được phục vụ bởi AP-2. Khi C di chuyển, nó gởi khung Probe đến AP-2 và được AP-2 trả lời bằng khung Probe Response. Tại thời điểm đó, C thích AP-2 hơn AP-2, do đó nó gia nhập vào điểm truy cập này. Cơ chế vừa được mô tả được gọi là cơ chế “quét chủ động” – active scanning, do nút chủ động dò tìm điểm truy cập. Các AP cũng thường xuyên gởi khung Beacon (đèn hiệu) để quảng cáo cho khả năng của mình, bao gồm tốc độ truyền được điểm truy cập hỗ trợ. Cơ chế này được gọi là “quét thụ động” – passive scanning, và một nút có thể chuyển sang điểm truy cập này đơn giản bằng cách gởi môt khung Association Request ngược lại AP. 5.5.5.4 Khuôn dạng khung H5.40 Khuôn dạng khung 802.11 Hầu hết các thông tin trong khung 802.11, như được vẽ trong H5.40, là đều như chúng ta mong muốn. Khung bao gồm địa chỉ nguồn và đích, mỗi cái dài 48 bits; dữ liệu tối đa 2312 bytes; và phần kiểm tra lỗi CRC 32 bits. Trường Control chứa ba trường con: Trường Type dài 6 bits – dùng để chỉ ra khung là khung dữ liêu, hay là khung RTS, hay là CTS, hoặc cũng được sử dụng bởi giải thuật quét; một cặp trường mỗi trường dài 1 bit gọi là ToDS và FromDS, sẽ được giải thích ngay sau đây. Điều kỳ dị trong khung 802.11 là nó chứa đến bốn địa chỉ. Cách thức thông dịch các địa chỉ này lại phụ thuộc vào việc thiết đặt các bít ToDS và FromDS trong trường Control. Điều này là để tính đến khả năng khung phải được chuyển tiếp qua hệ thống phân tán, có nghĩa là bên gởi nguyên thủy không nhất thiết phải là nút phát khung gần đây nhất. Cũng tương tự đối với địa chỉ bên nhận. Trong trường hợp đơn giản nhất, khi một nút gởi khung trực tiếp đến nút kia, cả hai bit DS đều có giá trị 0, Addr1 chứa địa chỉ nút đích, Addr2 chứa địa chỉ nút nguồn. Trong trường hợp phức tạp nhất, cả hai bit DS mang giá trị 1, chỉ ra rằng khung thông tin đi từ nút không dây qua hệ thống phân tán và rồi từ hệ thống phân tán đến nút không dây bên đích. Với cả hai bit DS được đặt, Addr1 định danh đích cuối cùng, Addr2 định danh nút gởi tạm thời (là nút đã chuyển khung từ hệ thống phân tán đến đích cuối cùng), Addr3 định danh nút đích tạm thời (là nút đã nhận khung từ nút không dây và trung chuyển khung xuyên qua hệ thống phân tán), Addr4 định danh nút gởi nguyên thủy. Trong ví dụ H5.37, Addr1=E, Addr2=AP-3, Addr3=AP-1, Addr4=A. Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 92
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 Chương 6: Tầng mạng (Network Layer) Mục đích Chương này nhằm giới thiệu cho người đọc những nội dung sau: • Vai trò của router trong việc xây dựng các liên mạng có phạm vi rộng và không đồng nhất về chuẩn của các mạng cục bộ thành phần • Các dịch vụ mà tầng mạng phải cung cấp cho tầng vận chuyển • Cơ chế hoạt động của router • Các vấn đề liên quan đến giải thuật chọn đường cho các router • Giới thiệu về bộ giao thức liên mạng IP Yêu cầu Sau khi học xong chương này, người đọc phải có được những khả năng sau: • Mô tả được sơ đồ tổng quát của một liên mạng ở tầng 3 và vai trò của router trong liên mạng này • Trình bày được các dịch vụ mà tầng mạng phải cung cấp cho tầng vận chuyển • Giải thích cơ chế truyền tải thông tin theo kỹ thuật truyền tải lưu và chuyển tiếp của các router • Giải thích được ý nghĩa của bảng chọn đường trong router • Phân biệt được các loại giải thuật chọn đường khác nhau • Cài đặt được các giải thuật chọn đường Dijkstra, Ford-Fulkerson, Distance Vector, Link state • Nêu lên được các phương pháp để chống tắc nghẽn trên mạng diện rộng • Biết cách thiết lập sơ đồ đánh địa chỉ IP cho mạng • Thực hiện được việc phân mạng con theo những yêu cầu khác nhau theo cả hai phương pháp : Phân lớp hoàn toàn và Vạch đường liên miền không phân lớp • Xây dựng được bảng chọn đường thủ công cho các router trong mạng IP • Nêu lên được ý nghĩa của các giao thức ARP, RARP và ICMP trong bộ giao thức IP Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 93
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 6.1 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. 6.2 Các vấn đề liên quan đến việc thiết kế tầng mạng 6.2.1 Kỹ thuật hoán chuyển lưu và chuyển tiếp (Store-and-Forward Switching) Xét một liên mạng như hình dưới đây H6.1 Kỹ thuật lưu và chuyển tiếp trên tầng mạng Trong đó các router nằm trong hình oval được nối lại với nhau bằng các đường truyền theo kiểu điểm nối điểm được gọi là các thiết bị của nhà cung cấp đường truyền (Carrier’s equipment). Các thiết bị nằm bên ngoài hình oval được gọi là các thiết bị của khách hàng (Customer’s Equipment). Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 94
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 Máy tính H1 được nối trực tiếp vào router A của nhà cung cấp đường truyền bằng một đường nối kết thường trực (lease line). Máy H2 nối kết vào một mạng LAN cục bộ. Trong mạng LAN có router F thuộc sở hữu của khách hàng. F được nối với router E của nhà cung cấp cũng bằng một đường nối kết thường trực. Cho dù cách thức nối kết vào mạng của các máy tính có thể khác nhau như trường hợp máy H1 và H2, nhưng cách thức các gói tin của chúng được truyền đi đều giống nhau. Một máy tính có một gói tin cần truyền đi sẽ gởi gói tin đến router gần nó nhất, có thể là router trên LAN của nó hoặc router của nhà cung cấp đường truyền. Gói tin được lưu lại ở đó và được kiểm tra lỗi. Kế đến gói tin sẽ được chuyển đến một router kế tiếp trên đường đi đến đích của gói tin. Và cứ tiếp tục như thế cho đến khi đến được máy nhận gói tin. Đây chính là kỹ thuật lưu và chuyển tiếp. 6.2.2 Các dịch vụ cung cấp cho tầng vận chuyển Các dịch vụ tầng mạng cung cấp cho tầng vận chuyển cần được thiết kế hướng đến các mục tiêu sau: Các dịch vụ này cần nên độc lập với kỹ thuật của các router. 1. Tầng vận chuyển cần được độc lập với số lượng, kiểu và hình trạng của các router hiện hành. 2. Địa chỉ mạng cung cấp cho tầng vận chuyển phải có sơ đồ đánh số nhất quán cho dù chúng là LAN hay WAN. Tầng mạng cung cấp hai dịch vụ chính là Dịch vụ không nối kết (Connectionless Service) và Dịch vụ định hướng nối kết (Connection – Oriented Service). Trong dịch vụ không nối kết, các gói tin được đưa vào subnet một cách riêng lẽ và được vạch đường một cách độc lập nhau. Không cần thiết phải thiết lập nối kết trước khi truyền tin. Các gói tin trong trường hợp này được gọi là thư tín (Datagram) và subnet được gọi là Datagram Subnet. Ngược lại trong dịch vụ định hướng nối kết, một đường nối kết giữa bên gởi và bên nhận phải được thiết lập trước khi các gói tin có thể được gởi đi. Nối kết này được gọi là mạch ảo (Virtual Circuit) tương tự như mạch vật lý được nối kết trong hệ thống điện thoại và subnet trong trường hợp này được gọi là virtual circuit subnet. 6.2.2.1 Cài đặt dịch vụ không nối kết ( Implementation of Connectionless Service) Xét hệ thống mạng như hình H6.2. Giả sử rằng quá trình P1 có nhiều thông điệp cần gởi cho quá trình P2. Khi đó P1 sẽ gởi các thông điệp này cho tầng vận chuyển và yêu cầu tầng vận chuyển truyền sang quá trình P2 trên máy tính H2. Tầng vận chuyển sẽ gắn thêm tiêu đề (header) của nó vào thông điệp và chuyển các thông điệp xuống tầng mạng. Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 95
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 Đích đến Bước kế tiếp H6.2 Hoạt động của Datagram subnet Giả sử rằng thông điệp gởi đi thì lớn gấp 4 lần kích thước tối đa của một gói tin, vì thế tầng mạng phải chia thông điệp ra thành 4 gói tin 1,2,3 và 4, và lần lượt gởi từng gói một đến router A bằng một giao thức điểm nối điểm như PPP chẳng hạn. Mỗi router có một bảng thông tin cục bộ chỉ ra nơi nào có thể gởi các gói tin để có thể đến được những đích đến khác nhau trên mạng. Mỗi mục từ của bảng chứa 2 thông quan trọng nhất đó là Đích đến (Destination) và ngỏ ra kế tiếp (Next Hop) cần phải chuyển gói tin đến để có thể đến được đích đến này. Ta gọi là bảng chọn đường (Routing Table). Ví dụ Lúc khởi đầu, router A có bảng chọn đường như hình H6.2 (lúc đầu). Khi gói tin 1,2 và 3 đến router A, nó được lưu tạm thời để kiểm tra lỗi. Sau đó chúng được chuyển tiếp sang router C vì theo thông tin trong bảng chọn đường của A. Gói tin 1 sau đó tiếp tục được chuyển đến E và kế đến là F. Sau đó nó được gói lại trong một khung của tầng liên kết dữ liệu và được chuyển đến máy H2 bởi mạng LAN. Các gói tin 2 và 3 cũng có cùng đường đi tương tự. Sau đó, do một số sự cố về đường truyền, router A cập nhật lại bảng chọn đường của mình như hình H6.2(lúc sau). Khi đó gói tin số 4 đến router A, nó sẽ chuyển gói tin này sang B để có thể đi được đến H2. Giải thuật chịu trách nhiệm quản lý thông tin trong bảng chọn đường cũng như thực hiện các quyết định về chọn đường được gọi là Giải thuật chọn đường (Routing algorithm). 6.2.2.2 Cài đặt dịch vụ định hướng nối kết (Connection – Oriented Service) Đối với dịch vụ nối kết định hướng chúng ta cần một mạch ảo trên subnet. Mục đích của việc sử dụng mạch ảo là để tránh phải thực hiện việc chọn lại đường đi mới cho mỗi gói tin gởi đến cùng một đích. Khi một nối kết được thực hiện, một đường đi từ máy tính gởi đến máy tính nhận được chọn như là một phần của giai đoạn thiết lập nối kết (Connection setup) và được lưu trong bảng chọn đường của các router nằm trên đường đi. Khi nối kết kết thúc, mạch ảo bị xóa. Với dịch vụ định hướng nối kết, mỗi gói tin có mang một số định dạng để xác định mạch ảo mà nó thuộc về. Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 96
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 H6.3 Hoạt động của Datagram subnet Như hình H6.3, máy tính H1 thực hiện một nối kết với máy tính H2 qua nối kết số 1. Nối kết này được ghi nhận trong mục từ đầu tiên trong bảng chọn đường của các router. Dòng đầu tiên trong bảng chọn đường của router A nói rằng: những gói tin mang số nhận dạng nối kết số 1 đến từ máy H1 phải được gởi sang router C với số nhận dạng nối kết là 1. Tương tự, cho các mục từ đầu tiên của router C và E. Điều gì xảy ra nếu máy tính H3 muốn nối kết với máy tính H2. Nó chọn số nhận dạng nối kết là 1, vì đây là nối kết đầu tiên đối với H3, và yêu cầu subnet thiết lập mạch ảo. Điều này đã làm cho các router phải thêm vào mục từ số 2 trong bảng chọn đường. Đối với router A, số nhận dạng nối kết với H3 là 1, trùng với nối kết với H1, không làm router A lẫn lộn vì A có thêm thông tin máy gởi là H1 hay H3. Tuy nhiên, đối với các router C, E và F thì không thể phân biệt được đâu là nối kết của H1 và đâu là nối kết của H3 nếu sử dụng số nhận dạng nối kết là 1 cho cả 2 nối kết. Chính vì thế A đã gán một số nhận dạng khác, là số 2, cho các gói tin gởi đến C có nguồn gốc từ H3. 6.2.2.3 So sánh giữa Datagram subnet và Virtual-Circuit subnet Bảng sau so sánh điểm mạnh và điểm yếu của 2 loại dịch vụ không nối kết và định hướng nối kết: Vấn đề Datagram Subnet Circuit Subnet Thiết lập nối kết Không cần Cần thiết Đánh địa chỉ Mỗi gói tin chứa đầy đủ địa chỉ Mỗi gói tin chỉ chứa số nhận dạng gởi và nhận nối kết có kích thước nhỏ. Thông tin trạng thái Router không cần phải lưu giữ Mỗi nối kết phải được lưu lại trong thông tin trạng thái của các nối bảng chọn đường của router. kết Chọn đường Mỗi gói tin có đường đi khác Đường đi được chọn khi mạch ảo nhau được thiết lập, sau đó tất cả các gói tin đều đi trên đường này. Ảnh hưởng khi router bị Không bị ảnh hưởng, ngoại trừ Tất cả các mạch ảo đi qua router bị hỏng gói tin đang trên đường truyền bị hỏng đều bị kết thúc hỏng Chất lượng dịch vụ Khó đảm bảo Có thể thực hiện dễ dàng nếu có đủ tài nguyên gán trước cho từng nối kết Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 97
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 Điều khiển tắc nghẽn Khó điều khiển Có thể thực hiện dễ dàng nếu có đủ tài nguyên gán trước cho từng nối kết 6.3 Giải thuật chọn đường 6.3.1 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. A 6 1 3 2 F 1 E B 4 1 9 C D H6.4 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. 6.3.2 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 6.3.3 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. Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 98
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 6.3.4 Các giải thuật tìm đường đi 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: o Số lượng các router trung gian phải đi qua (HOP) o Độ trì quản trung bình của các gói tín o 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. H6.5 Mô hình hóa mạng thành đồ thị 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. 6.3.4.1 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: o S là nút nguồn cho trước o 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. o Di: là độ dài đường đi ngắn nhất từ nút nguồn S đến nút i. o 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. o Pj là nút cha của của nút j. Bước 1: Khởi tạo o N={S}; Ds=0; o Với ∀i≠S: Di=lsi , Pi=S Bước 2: Tìm nút gần nhất kế tiếp o Tìm nút i ∉ N thoả Di= min (Dj) với j ∉ N o Thêm nút i vào N. o 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 o Bước 3: Tính lại giá đường đi nhỏ nhất Với mỗi nút j ∉ 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: H6.6 Hình trạng mạn Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 99
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 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 H6.7. 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 H6.7 Cây đường đi ngắn nhất từ nút 1 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. 6.3.4.2 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 o d là nút đích cho trước o Di là chiều dài đường đi ngăn nhất từ nút i đến nút d. o Ci là nút con của nút i Bước 1: Khởi tạo: o Gán Dd = 0; o Vớ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 o Di= min{ lij+ Dj} với ∀j≠i => Ci = j; o Lặ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: H6.8 Hình trạng mạng Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 100
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 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ư H6.9. 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à H6.9 Cây đường đi ngắn nhất về gởi các đường đi này đến từng nút trên mạng. nút 6 6.3.5 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 H6.10 B C A D E F G Hình 6.10 Một mạng làm ví dụ trong giải thuật Distance-Vector Trong ví dụ này, chi phí trên mỗi đường nối đều được đặt là 1. Chúng ta có thể biểu diễn sự hiểu biết của các nút về khoảng cách từ chúng đến các nút khác như trong bảng H6.11 Thông tin được Khoảng cách đến nút lưu tại các nút A B C D E F G A 0 1 1 ∞ 1 1 ∞ B 1 0 1 ∞ ∞ ∞ ∞ C 1 1 0 1 ∞ ∞ ∞ D ∞ ∞ 1 0 ∞ ∞ 1 E 1 ∞ ∞ ∞ 0 ∞ ∞ F 1 ∞ ∞ ∞ ∞ 0 1 G ∞ ∞ ∞ 1 ∞ 1 0 H6.11 Các khoảng cách ban đầu được lưu tại mỗi nút Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 101
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 Chúng ta có thể xem mỗi một hàng trong bảng 6.11 như là một danh sách các khoảng cách từ một nút đến tất cả các nút khác. Khởi đầu, mỗi nút đặt giá trị 1 cho đường nối kết đến các nút láng giềng kề nó, ∞ cho các đường nối đến tất cả các nút còn lại. Do đó, lúc đầu A tin rằng nó có thể tìm đến B qua một bước nhảy (hop) và rằng nó không thể đi đến D được. Bảng vạch đường lưu tại A thể hiện những niềm tin mà A có được, ngoài ra còn lưu thêm nút kế tiếp mà A cần phải đi ra để đến một nút nào đó. Khởi đầu, bảng vạch đường của nút A trông giống như trong bảng 6.12 Đích Chi phí Nút kế tiếp (Destination) (Cost) (Next Hop) B 1 B C 1 C D ∞ - E 1 E F 1 F G ∞ - H6.12 Bảng vạch đường khởi đầu tại nút A Bước kế tiếp trong giải thuật vạch đường Distance-Vector là: mỗi nút sẽ gởi một thông điệp đến các láng giềng liền kề nó, trong thông điệp đó chứa danh sách các khoảng cách mà cá nhân nút tính được. Ví dụ, nút F bảo nút A rằng F có thể đi đến nút G với chi phí là 1; A cũng biết được rằng nó có thể đến F với chi phí là 1, vì thế A cộng các chi phí lại thành chi phí đi đến G là 2 thông qua F. Tổng chi phí là 2 này nhỏ hơn chi phí vô cùng lúc đầu, do đó A ghi lại nó có thể đi đến G thông qua F với chi phí là 2. Tương tự, A học được từ C rằng, nó có thể đi đến D thông qua C với chi phí là 2, và chi phí này nhỏ hơn chi phí cũ là vô cùng. Cùng lúc A cũng học từ C rằng, nó có thể đi đến B thông qua C với chi phí là 2, nhưng chi phí này lại lớn hơn chi phí cũ là 1, vì thế thông tin mới này bị bỏ qua. Tại thời điểm này, A có thể cập nhật lại bảng chọn đường của nó với chi phí và nút ra kế tiếp để có thể đi đến tất cả các nút khác trong mạng. Kết quả được cho trong bảng H6.13 Đích Chi phí Nút kế tiếp (Destination) (Cost) (Next Hop) B 1 B C 1 C D 2 C E 1 E F 1 F G 2 F H.6.13 Bảng vạch đường cuối cùng tại nút A Nếu không có sự thay đổi về hình trạng mạng nào, chỉ cần vài cuộc trao đổi thông tin vạch đường giữa các nút trong mạng thì mọi nút đều có được thông tin vạch đường hoàn hảo. Quá trình đem thông tin vạch đường nhất quán đến mọi nút trong mạng được gọi là sự hội tụ (convergence). Hình 6.14 chỉ ra thông tin về chi phí cuối cùng từ một nút đến các nút khác trong mạng khi quá trình vạch đường đã hội tụ. Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 102
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Mạng Máy Tính – V1.0 Thông tin được Khoảng cách đến nút lưu tại các nút A B C D E F G A 0 1 1 2 1 1 2 B 1 0 1 2 2 2 3 C 1 1 0 1 2 2 2 D 2 2 1 0 3 2 1 E 1 2 2 3 0 2 3 F 1 2 2 2 2 0 1 G 2 3 2 1 3 1 0 H6.14 Các khoảng cách cuối cùng được lưu tại mỗi nút Nét đẹp của loại giải thuật phân tán như trên nằm ở chỗ nó cho phép tất cả các nút đạt được thông tin vạch đường mà không cần phải có sự hiện diện của bộ điều khiển trung tâm nào. Còn có vài chi tiết làm cho giải thuật Distance-Vector hoàn hảo hơn. Thứ nhất, chú ý rằng có hai tình huống khác nhau mà tại đó một nút quyết định gởi thông tin vạch đường của mình cho các nút láng giềng kề bên. Tình huống đầu tiên là sự cập nhật theo chu kỳ (periodic update). Trong tình huống này, mỗi nút tự động gởi bản cập nhật thường xuyên, ngay cả khi không có thay đổi gì trong đó cả. Điều này giúp cho các nút khác biết được nút hiện tại đang còn sống. Vả lại việc cập nhật thường xuyên còn giúp cho các nút láng giềng có thể có được thông tin vạch đường nhanh chóng trong trường hợp thông tin của chúng bị mất. Tần số phát thông tin vạch đường đi có thể khác nhau tùy vào giải thuật, chúng thường có giá trị từ vài giây đến vài phút. Tình huống thứ hai gọi là sự cập nhật do bị kích hoạt (triggered update). Tình huống này xảy ra mỗi khi có sự thay đổi thông tin trong bảng vạch đường của nút. Nghĩa là mỗi khi bảng vạch đường có sự thay đổi, nút sẽ gởi bản cập nhật này cho các láng giềng của mình. Bây giờ ta xem xét điều gì xảy ra khi một đường nối kết hay một nút bị hỏng. Những nút đầu tiên phát hiện ra điều này sẽ gởi thông tin vạch đường mới cho láng giềng của chúng ngay, và thông thường hệ thống sẽ ổn định với tình trạng mới một cách nhanh chóng. Còn đối với câu hỏi làm sao nút phát hiện ra sự cố, có nhiều câu trả lời khác nhau. Cách tiếp cận thứ nhất là: một nút liên tục kiểm tra đường nối tới các nút láng giềng khác bằng cách gởi các gói tin điều khiển tới chúng và kiểm tra xem nó có nhận được các gói tin trả lời hay không. Cách tiếp cận khác là: một nút phát hiện ra một đường nối kết (hay nút ở đầu kia của đường nối) gặp sự cố khi nó không nhận được thông tin vạch đường một cách định kỳ từ láng giềng của nó. Ví dụ, xem xét điều gì sẽ xảy ra khi F phát hiện ra đường nối từ nó đến G bị hỏng. Đầu tiên, F đặt chi phí của đường nối từ nó đến A thành vô cùng và gởi thông tin này đến A. Do A đã biết là cần 2 bước để đi từ nó đến G thông qua F, A sẽ đặt lại chi phí từ nó đến G là vô cùng. Tuy nhiên, với bản cập nhật kế tiếp từ C, A phát hiện ra rằng có một đường đi dài 2 hops từ C đến G, do đó nó sẽ cập nhật lại đường đi từ nó đến G dài 3 hops thông qua C. Và khi A quảng cáo thông tin này cho F, F lại cập nhật lại đường đi dài 4 hops đến G thông qua A. Không may là: một số tình huống phát sinh lỗi khác lại làm cho mạng mất ổn định nghiêm trọng. Giả sử nối kết từ A đến E bị đứt. Trong những chu kỳ cập nhật sau, A thông báo đường đi từ nó đến E dài vô cùng, nhưng B và C lại quảng cáo đường đi từ chúng đến E dài 2 hops. Nếu các bản cập nhật được định thời để phát cùng lúc, B sẽ sửa lại độ dài đường đi từ nó đến E là 3 thông qua C, C sửa lại độ dài đường đi từ nó đến E là 3 thông qua B. Sau đó A lại nghe B và C quảng cáo độ dài đường đi từ chúng đến E là 3 và giả sử A chọn B là nút kế tiếp để đi đến E, nó sẽ cập nhật lại độ dài đoạn đường là 4. Đến chu kỳ kế tiếp, B nghe C nói độ dài từ C đến E là 3 nên cập nhật lại độ dài đường đi từ B đến E là 4 thông qua C, C thì làm ngược lại: sửa lại con đường từ nó đến E là 4 thông qua B. Rồi lại đến lượt A nghe B sửa lại độ dài từ A đến E là 5 thông qua B. Sự thể sẽ tiếp diễn cho đến khi các độ dài tăng đến một số có thể coi là vô cùng. Nhưng tại thời điểm này, không nút nào biết là E không thể đến được, và các bảng vạch đường trong mạng luôn không ổn định. Tình huống này được gọi là vấn đề “đếm tới vô cùng” (count-to-infinity problem). Biên Sọan: Th.s Ngô Bá Hùng – Ks Phạm Thế Phi - 01/2005 103