Bài giảng Mạng thông tin
TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT HƯNG YÊN
KHOA ĐIỆN-ĐIỆN TỬ
BÀI GIẢNG
MẠNG THÔNG TIN
Hưng Yên 2015
(Tài liệu lưu hành nội bộ)
KHOA ĐIỆN-ĐIỆN TỬ
ĐHSP KT HƯNG YÊN
Chƣơng 1. CÁC KHÁI NIỆM CƠ BẢN VỀ MẠNG THÔNG TIN
1.1. TỔNG QUAN VỀ MẠNG THÔNG TIN
Nội dung chính của chƣơng này đƣợc trình bày theo các mục chính và đƣợc sắp xếp theo
trình, cụ thể: Thông tin và truyền thông đây là một trong những vấn vấn đề đang đƣợc xã
hội quan tâm trong nền kinh tế mới, nền kinh tế thông tin, nền kinh tế trí thức, nền kinh tế
học hỏi và nền kinh tế số; trang bị về cái nhìn tổng quát về mạng số liệu; tổ chức về mạng
truyền số liệu hiện đại, các kỹ thuật đƣợc dùng trong truyền số liệu và những vấn đề căn
bản trong chuẩn hóa và mô hình tham chiếu của mạng
1.1.1 Thông tin và truyền thông
Thông tin liên lạc đóng vai trò hết sức quang trọng trong cuộc sống, hầu hết chúng ta luôn
gắn liền với một vài dạng thông tin nào đó. Các dạng trao đổi tin có thể nhƣ: đàm thoại
ngƣời với ngƣời, đọc sách, gửi và nhận thƣ, nói chuyện qua điện thoại, xem phim hay
truyền hình, xem triển lãm tranh , tham dự diễn đàn . . .
Có hàng nghìn ví dụ khác nhau về thông tin liên lạc, trong đó gia công chế biến để truyền
đi trong thông tin số liệu là một phần đặc biệt trong lĩnh vực thông tin.
Máy tính A
Máy tính B
Thông tin user đến user
Thông tin máy
tính đến máy tính
AP
AP
Hệ thống phục
truyền tin
Hệ thống phục vụ
phục truyền tin
Thông tin máy
tính đến mạng
Mạng truyền số liệu
Hình 1.1. Một hệ thống thông tin cơ bản
ở đây: AP- Applicayion process- Quá trình ứng dụng
Từ các ví dụ trên chúng ta nhận thấy rằng mỗi hệ thống truyền tin đều có các đặc trƣng
riêng nhƣng có một số đặc tính chung cho tất cả các hệ thống. Đặc trƣng chung có tính
nguyên lý là tất cả các hệ thống truyền tin đều nhằm mục đích chuyển tải thông tin từ
điểm này đến điểm khác. Trong các hệ thống truyền số liệu, thƣờng gọi thông tin là dữ
liệu hay thông điệp. Thông điệp có nhiều dạng khác nhau, để truyền thông điệp từ một
điểm này đến điểm khác cần phải có sự tham gia của 3 thành phần của hệ thống: nguồn
TS. NGUYỄN VĂN VINH
-3-
MẠNG THÔNG TIN
KHOA ĐIỆN-ĐIỆN TỬ
ĐHSP KT HƯNG YÊN
tin là nơi phát sinh và chuyển thông điệp lên môi trƣờng truyền; môi trƣờng truyền là
phƣơng tiện mang thông điệp tới đích thu. Các phần tử này là yêu cầu tối thiểu trong bất
cứ quá trình truyền tin nào. Nếu một trong các thành phần này không tồn tại, truyền tin
không thể xảy ra. Một hệ thống truyền tin thông thƣờng đƣợc miêu tả trên hình 1.1.
Các thành phần cơ bản có thể xuất hiện dƣới dạng khác nhau tuỳ thuộc vào hệ thống. Khi
xây dựng các thành phần của một hệ thống truyền tin, cần phải xác định một số các yếu tố
liên quan đến phẩm chất hoạt động của nó.
Để truyền tin hiệu quả các chủ để phải hiểu đƣợc thông điệp. Nơi thu nhận thông điệp
phải có khả năng dịch thông điệp một cách chính xác. Điều này là hiển nhiên bởi vì trong
giao tiếp hàng ngày nếu chúng ta dùng một từ mà ngƣời ta không thể hiểu thì hiệu quả
thông tin không đạt yêu cầu. Tƣơng tự, nếu máy tính mong muốn thông tin đến với tốc độ
chỉ định và ở một dạng mã nào đó nhƣng thông tin lại đến với tốc độ khác và với dạng mã
khác thì rõ ràng không thể đạt đƣợc hiệu quả truyền.
Các đặc trƣng toàn cục của một hệ thống truyền đƣợc xác định và bị giới hạn bởi các
thuộc tính riêng của nguồn tin, của môi trƣờng truyền và đích thu. Nhìn chung, dạng
thông tin cần truyền quyết định kiểu nguồn tin, môi trƣờng và đích thu.
Trong một hệ thống truyền, hiện tƣợng nhiễu có thề xảy ra trong tiến trình truyền và
thông điệp có thể bị ngắt quãng. Bất kỳ sự xâm nhập không mong muốn nào vào tín hiệu
đều bị gọi là nhiễu. Có nhiều nguồn nhiễu và nhiều dạng nhiễu khác nhau.
Hiểu biết đƣợc các nguyên tắc căn bản về truyền tin sẽ giúp chúng ta dễ dàng tiếp cận
một lĩnh vực đặc biệt hấp dẫn đó là thông tin số liệu.Thông tin số liệu liên quan đến một
tổ hợp nguồn tin, môi trƣờng và máy thu trong các kiểu mạng truyền số liệu khác nhau.
1.1.2 Các dạng thông tin và xử lý thông tin
Tất cả những gì mà con ngƣời muốn trao đổi với nhau đƣợc hiểu là thông tin những
thông tin nguyên thuỷ này đƣợc gia công chế biến để truyền đi trong không gian đƣợc
hiểu là tín hiệu. Tuỳ theo việc sử dụng đƣờng truyền, tín hiệu có thể tạm chia tín hiệu
thành hai dạng: tín hiệu điện-từ và tín hiệu không phải điện từ. Việc gia công tín hiệu cho
phù hợp với mục đích và phù hợp với đƣờng truyền vật lý đƣợc gọi là xử lý tín hiệu.
Ngày nay với sự phát triển của công nghệ tin học đã tạo ra một công nghệ mới về truyền
số liệu. Máy tính với những tính năng vô cùng to lớn đã trở thành hạt nhân trong việc xử
lý thông tin, điều khiển các quá trình truy nhập số liệu, máy tính và các hệ thống thông tin
tạo thành một hệ thống truyền số liệu.
Có 2 nguồn thông tin đó là thông tin tƣơng tự và thông tin số. Trong đó nguồn thông tin
tƣơng tự liên tục theo sự thay đổi của giá trị vật lý thể hiện thông tin với đặc tính chất
TS. NGUYỄN VĂN VINH
-4-
MẠNG THÔNG TIN
KHOA ĐIỆN-ĐIỆN TỬ
ĐHSP KT HƯNG YÊN
lƣợng nhƣ tiếng nói, tín hiệu hình ảnh , còn nguồn thông tin số là tín hiệu gián đoạn thể
hiện thông tin bởi nhóm các giá trị gián đoạn xác định đặc tính chất lƣợng bằng quan hệ
với thời gian nhƣ tín hiệu số liệu.
Thông tin số có nhiều ƣu điểm hơn so với thông tin tƣơng tự nhƣ : thông tin số có nhiều
khả năng chống nhiễu tốt hơn vì nó có các bộ lặp để tái tạo lại tín hiệu, cung cấp chất
lƣợng truyền dẫn tốt hơn với các khoảng cách, nó kết hợp đƣợc mọi nguồn dịch vụ hiện
đang có, nó tạo ra đƣợc một tổ hợp truyền dẫn số và tổng đài số. Những phần tử bán dẫn
dùng trong truyền dẫn số là những mạch tổ hợp nó đƣợc sản xuất hàng loạt, và mạng liên
lạc trở thành mạng thông minh vì dễ chuyển đổi tốc độ cho các loại dịch vụ khác nhau
thay đổi thủ tục, xử lý tín hiệu số (DSP) chuyển đổi phƣơng tiện truyền dẫn ...
Hệ thống thông tin số cho phép thông tin điều khiển đƣợc cài đặt vào và tách dòng thông
tin thực hiện một cách độc lập với với bản chất của phƣơng tiện truyền tin ( cáp đồng trục,
cáp sợi quang, vi ba, vệ tinh..),. Vì vậy thiết bị báo hiệu có thể thiết kế riêng biệt với hệ
thống truyền dẫn.
Chức năng điều khiển có thể thay đổi mà không phụ thuộc vào hệ thống truyền dẫn,
ngƣợc lại hệ thống có thể nâng cấp không ảnh hƣởng tới các chức năng điều khiển ở cả 2
đầu của đƣờng truyền
1.2 Khái quát mạng truyền số liệu
Giao tiếp
Giao tiếp
DTE-DCE
DTE-DCE
DTE
DCE
Kênh truyền tin
DCE
DTE
Hệ thống truyền
(nhận) tin
Hệ thống nhận
(truyền) tin
Hình 1.2. Mô hình mạng truyền số liệu hiện đại
Ngày nay với sự phát triển của kỹ thuật và công nghệ đã tạo ra một bƣớc tiến dài trong
lĩnh vực truyền số liệu. Sự kết hợp giữa phần cứng, các giao thức truyền thông các thuật
toán đã tạo ra các hệ thống truyền số liệu hiện đại, những ký thuật cơ sở vẫn đƣợc dùng
nhƣng chúng đƣợc xử lý tinh vi hơn. Về cơ bản một hệ thống truyền số liệu hiện đại mô
tả nhƣ hình 1.2
TS. NGUYỄN VĂN VINH
-5-
MẠNG THÔNG TIN
KHOA ĐIỆN-ĐIỆN TỬ
ĐHSP KT HƯNG YÊN
a. DTE (Data Terminal Equipment – Thiết bị đầu cuối dữ liệu)
Đây là thiết bị lƣu trữ và xử lý thông tin. Trong hệ thống truyền số liệu hiện đại thi DTE
thƣờng là máy tính hoặc máy Fax hoặc là trạm cuối (terminal). Nhƣ vậy tất cả các ứng
dụng của ngƣời sử dụng (chƣơng trình, dữ liệu) đều nằm trong DTE Chức năng của DTE
thƣờng lƣu trữ các phần mềm ứng dụng , đóng gói dữ liệu rồi gửi ra DCE hoặc nhận gói
dữ liệu từ DCE theo một giao thức (protocol) xác định DTE trao đổi với DCE thông qua
một chuẩn giao tiếp nào đó. Nhƣ vậy mạng truyền số liệu chính là để nối các DTE lại cho
phép chúng ta phân chia tài nguyên, trao đổi dữ liệu và lƣu trữ thông tin dùng chung
b. DCE (Data Circuit terminal Equipment- Thiết bị cuối kênh dữ liệu)
Đây là thuật ngữ dùng để chỉ các thiết bị dùng để nối các DTE với các đƣờng (mạng)
truyền thông nó có thể là một Modem, Multiplexer, Card mạng...hoặc một thiết bị số nào
đó nhƣ một máy tính nào đó trong trƣờng hợp máy tính đó là một nút mạng và DTE đƣợc
nối với mạng qua nút mạng đó. DCE có thể đƣợc cài đặt bên trong DTE hoặc đứng riêng
nhƣ một thiết bị độc lập.
Trong thiết bị DCE thƣờng có các phần mềm đƣợc ghi vào bộ nhớ ROM phần mềm và
phần cứng kết hợp với nhau để thực hiện nhiệm vụ của nó vẫn là chuyển đổi tín hiệu biểu
diễn dữ liệu của ngƣời dùng thành dạng chấp nhận đƣợc bởi đƣờng truyền. Giữa 2 thiết
bị DTE việc trao đổi dữ liệu phải tuân thủ theo chuẩn, dữ liệu phải gửi theo một Format
xác định. Thí dụ nhƣ chuẩn trao đổi dữ liệu tầng 2 của mô hình 7 lớp là HDLC
(High level Data Link Control) Trong máy Fax thì giao tiếp giữa DTE và DCE đã thiết kế
và đƣợc tích hợp vào trong một thiết bị, phần mềm điều khiển đƣợc cài đặt trong ROM.
c. Kênh truyền tin
Kênh truyền tin là môi trƣờng mà trên đó 2 thiết bị DTE trao đổi dữ liệu với nhau trong
phiên làm việc
DTE
C
D
E
F
DTE
Cáp đồng
trục
Cáp sợi
quang
Hình 1.3. Kênh thông tin
ở đây: C, D-Modem; E, F- Transducer
Trong môi trƣờng thực này 2 hệ thống đƣợc nối với nhau bằng một đoạn cáp đồng trục và
một đoạn cáp sợi quang, modem C để chuyển đổi tín hiệu số sang tín hiệu tƣơng tự để
truyền trong cáp đồng trục modem D lại chuyển tín hiệu đó thành tín hiệu số và qua
Tranducer E để chuyển đổi từ tín hiệu điện sang tín hiệu quang để truyền trên cáp sợi
TS. NGUYỄN VĂN VINH
-6-
MẠNG THÔNG TIN
KHOA ĐIỆN-ĐIỆN TỬ
ĐHSP KT HƯNG YÊN
quang cuối cùng Tranducer F lại chuyển tín hiệu quang thành tín hiệu điện để tới DTE
1.4. Mạng truyền số liệu
Mạng truyền số liệu bao gồm hai hay nhiều hệ thống truyền (nhận) tin nhƣ hình 1.2 đƣợc
ghép nối với nhau theo nhiều hình thức nhƣ phân cấp hoặc phân chia thành các trung tâm
xử lý trao đổi tin với các chức năng riêng ...
Mạng truyền số liệu là một hệ thống nhằm kết nối các máy tính lại với nhau, sự thông tin
giữa chúng đƣợc thực hiện bởi các giao thức đã đƣợc chuẩn hoá, có nghĩa các phần mềm
trong các máy tính khác nhau có thể cùng nhau giải quyết một công việc hoặc trao đổi
thông tin với nhau.
Các ứng dụng tin học ngày càng rộng rãi do đó đã đẩy các hƣớng ứng dụng mạng xử lý số
liệu, mạng đấu nối có thể có cấu trúc tuyến tính cấu trúc vòng cấu trúc hình sao... Cấu
trúc mạng phải có khả năng tiếp nhận các đặc thù khác nhau của các đơn vị tức là mạng
phải có tính đa năng, tính tƣơng thích.
Mạng số liệu đƣợc thiết kế nhằm mục đích có thể nối nhiều thiết bị đầu cuối với nhau. Để
truyền số liệu ta có thể dùng mạng điện thoại hoặc dùng đƣờng truyền riêng có tốc độ cao.
Dịch vụ truyền số lỉệu trên kênh thoại là một trong các dịch vụ đầu tiên của việc truyền số
liệu. Trên mạng này có thể có nhiều máy tính cùng chủng loại hoặc khác loại đƣợc ghép
nối lại với nhau, khi đó cần giải quyết những vấn đề phân chia tài nguyên. Để các máy
tính ở các đầu cuối có thể làm việc đƣợc với nhau cần phải có cùng một protocol nhất
định.
Dạng thức của phƣơng tiện truyền số liệu đƣợc qui định bởi bản chất tự nhiên của ứng
dụng, bởi số lƣợng máy tính liên quan và khoảng cách vật lý giữa chúng. Các dạng truyền
số liệu trên có các dạng sau:
a. Nếu chỉ có hai máy tính và cả hai đều đặt ở một văn phòng, thì phƣơng tiện truyền số
liệu có thể chỉ gồm một liên kết điểm nối đơn giản, hình 1.4. Tuy nhiên, nếu chúng liên
kết ở những vị trí khác nhau trong một thành phố hay một quốc gia thì phải cần đến các
phƣơng tiện truyền tải công cộng. Mạng điên thoại công cộng đƣợc dùng nhiều nhất,
trong trƣờng hợp này sẽ cần đến bộ thích nghi gọi là Modem. Sắp xếp truyền theo dạng
này đƣợc trình bày trên hình1.4
TS. NGUYỄN VĂN VINH
-7-
MẠNG THÔNG TIN
KHOA ĐIỆN-ĐIỆN TỬ
ĐHSP KT HƯNG YÊN
AP
AP
Hệ thống phục
truyền tin
Hệ thống phục vụ
phục truyền tin
PSTN
Modem
Modem
Hình 1.4. Truyền số liệu nối qua mạng điện thoại công cộng dùng modem
b. Khi cần nhiều máy tính trong một ứng dụng, một mạng chuyển mạch sẽ đƣợc dùng cho
phép tất cả các máy tính có thể liên lạc với nhau vào bất cứ thời điểm nào. Nếu tất cả máy
tính đều nằm trong một toà nhà , có thể xây dựng một mạng riêng .Một mạng nhƣ vậy
đƣợc xem nhƣ mạng cục bộ LAN (Local Area Network) .Nhiều chuẩn mạng LAN và các
thiết bị liên kết đã đƣợc tạo ra cho các ứng dụng thực tế . Hai hệ thống mạng Lan cơ bản
đƣợc trình bày trên hình 1.5
AP
AP
Hệ thống phục
truyền tin
Hệ thống phục vụ
phục truyền tin
Hình 1.5. Các hệ thống LAN cơ bản (liên kết LAN qua backbone trong một văn phòng)
Khi máy tính đƣợc đặt ở nhiều nơi cách xa nhau cần liên lạc với nhau, phải dùng đến các
phƣơng tiện công cộng .Việc liên kết máy tính này tạo nên một mạng rộng lớn, đƣợc gọi
là mạng diện rộng WAN (Wide Area Network). Kiểu mạng WAN đƣợc dùng phụ thuộc
vào tƣờng ứng dụng tự nhiên.
Ví dụ nếu tất cả các máy tính đều thuộc về một công ty và có yêu cầu truyền một số lƣợng
dữ liệu quan trọng giữa các điểm , thì giải pháp đơn giản nhất cho vắn đề là thuê các
TS. NGUYỄN VĂN VINH
-8-
MẠNG THÔNG TIN
KHOA ĐIỆN-ĐIỆN TỬ
ĐHSP KT HƯNG YÊN
đƣờng truyền từ nhà cung cấp phƣơng tiện truyền dẫn và xây dựng hệ thống chuyển mạch
riêng tại một đIểm để tạo thành mạng tƣ nhân.
Các giải pháp thuê kênh chỉ hiệu quả đối với các công ty lớn vì có tải hữu ích để cân đối
với giá thuê kênh. Trong hầu hết các trƣờng hợp khác đều cần đến các mạng truyền dẫn
công cộng. Bên cạnh việc cung cấp dịch vụ điện thoại công cộng, ngày nay hầu hết các
nhà cung cấp dịch vụ truyền dẫn đều cung cấp một dịch vụ chuyển mạch số liệu mang
tính công cộng. Thật ra các mạng này tƣơng tự nhƣ mạng PSTN là đƣợc liên kết quốc tế,
chỉ khác ở chỗ đƣợc thiết kế chuyên cho truyền số liệu. Nhƣ vậy các ứng dụng liên quan
đến máy tính đƣợc phục vụ bởi mạng số liệu chuyển mạch công cộng PSDN. Ngoài ra
còn có thể chuyển đổi các mạng PSTN có sẵn sao cho có thể truyền đƣợc số liệu mà
không cần dùng modem. Các mạng này hoạt động trong chế độ số (digital) hoàn toàn
đƣợc gọi là mạng số liên kết đa dịch vụ ISDN
1.4.1. Phân loại mạng truyền số liệu
Mạng truyền số liệu đa dạng về chủng loại cũng nhƣ về số lƣợng , có nhiều cách phân
chia mạng số liệu, bao gồm:
a. Phân loại theo địa lý: Mạng nội bộ, Mạng diện rộng và Mạng toàn cầu
b. Phân loại theo tính chất sử dụng mạng: Mạng truyền số liệu kí sinh và Mạng truyền số
liệu chuyên dụng.
c. Phân loại theo topo mạng: Mạng tuyến tính, Mạng hình sao và Mạng vòng
d. Phân loại theo kỹ thuật: Mạng chuyển mạch kênh, Mạng chuyển mạch gói và Mạng
chuyển mạch thông báo
1.4.2. Kỹ thuật chuyển mạch giữa các node trong mạng
Để thực hiện việc liên lạc giữ các thuê bao ngƣời ta tạo ra mạng liên lạc với các NODE.
Các thuê bao đƣợc nối đến các node . các thuê bao đƣợc nối vào mạng thông qua các
Node. Số lƣợng các node phụ thuộc vào độ lớn của mạng, nhƣ vậy mỗi thuê bao chị cần
một cổng I/O.
Mỗi mạng bao gồm các Node , các node đƣợc nối với nhau , số liệu sẽ truyền từ ngƣời
gửi đến ngƣời nhận theo con đƣờng thông qua mạng, các Node đƣợc nối với nhau theo
hƣớng truyền, số liệu đƣợc định đƣờng từ Node này sang node này sang node khác.
a. Kỹ thuật chuyển mạch kênh
Liên lạc thông qua chuyển mạch kênh đặc trƣng bởi việc cung cấp các đƣờng nối cố định
giữa 2 thuê bao. Sự liên lạc qua mạng chuyển mạch kênh bao gồm 3 giai đoạn : xác lập,
truyền số liệu và giải phóng mạch
TS. NGUYỄN VĂN VINH
-9-
MẠNG THÔNG TIN
KHOA ĐIỆN-ĐIỆN TỬ
* Xác lập mạch
ĐHSP KT HƯNG YÊN
Trƣớc khi có thể truyền số liệu , đƣờng truyền cần đƣợc thiết lập, Từ thuê bao truy nhập
vào một node, node này cần phải tìm các nhánh đi qua một số node khác để đến đƣợc thuê
bao bị gọi việc tìm kiếm này dựa vào các thông tin về tìm đƣờng và các thông số khác,
cuối cùng khi 2 node thuộc thuê bao gọi và bị gọi đƣợc nối với nhau nó cần kiểm tra xem
node thuộc thuê bao bị gọi có bận không. Nhƣ vậy là con đƣờng nối từ thuê bao gọi đến
thuê bao bị gọi đã đƣợc thiết lập
* Truyền số liệu
Thông tin bắt đầu truyền từ điểm A đến điểm E có thể trong dạng số hoặc tƣơng tự qua
điểm nối mạch bên trong mỗi node, sự nối mạch cho phép truyền 2 chiều toàn phần và dữ
liệu có thể truyền 2 chiều.
* Giải phóng mạch
Sau khi hoàn thành sự truyền, có tín hiệu báo của thuê bao gọi (A) hoặc bị gọi (E) báo
cho các node trung gian giải phóng sự nối mạch, đƣờng nối từ A đến E không còn nữa.
Đƣờng nối đƣợc thiết lập trƣớc khi truyền dữ liệu nhƣ vậy dung lƣợng các kênh cần phải
dự trữ cho mỗi cặp thuê bao và ở mỗi node cũng phải có lƣợng chuyển mạch tƣơng ứng
bên trong để bảo đảm bảo đƣợc sự yêu cầu nối mạch. Trong bộ chuyển mạch số lƣợng
kênh nối phải bảo đảm bảo suốt cả quá trình yêu cầu nối cho dù có hay không có dữ liệu
truyền qua.
Tuy nhiên khi đƣờng nối giữa 2 thuê bao đƣợc nối thì dữ liệu đƣợc truyền trên một
đƣờng cố định.
b. Kỹ thuật chuyển mạch thông báo
Chuyển mạch kênh có 2 nhƣợc điểm:
- 2 thuê bao cần phải hoạt động trong cùng thời gian truyền
- Những nguồn cung cấp cũng phải ổn định và cung cấp qua mạng giữa 2 thuê bao
Hiện nay những bức điện báo, thƣ điện tử, Files của máy tính đƣợc gọi là những thông
báo và nó đƣợc truyền qua mạng nhƣ sự trao đổi những dữ liệu số đƣợc trao đổi 2 chiều
giữa các thuê bao.
Một trong những loại mạch để phục vụ sự trao đổi thông tin đó đƣợc gọi là chuyển mạch
thông báo.
Với chuyển mạch thông báo không tồn tại sự thiết lập và cung cấp lộ trình cố định giữa 2
thuê bao, mỗi thuê bao muốn truyền một thông báo, nó sẽ gán địa chỉ của ngƣời nhận vào
thông báo. Thông báo sẽ đƣợc chuyển qua mạng từ node này qua node khác.Tại mỗi node
thông báo đƣợc nhận tạm giữ và chuyển sang node khác. Các node thông thƣờng là những
TS. NGUYỄN VĂN VINH
-10-
MẠNG THÔNG TIN
KHOA ĐIỆN-ĐIỆN TỬ
ĐHSP KT HƯNG YÊN
máy tính nó giữ thông báo ở bộ đệm. Thời gian trễ ở mỗi bộ đệm bao gồm cả thời gian
nhận thông báo vào node và thời gian xếp hàng chờ để đến lƣợt mình đƣợc chuyển đến
node sau.
Hệ thống chuyển mạch thông báo là hệ thống luôn giữ và chuyển tiếp.
c. Chuyển mạch gói
Chuyển mạch gói gần giống chuyển mạch thông báo. Chỗ khác nhau cơ bản là độ dài của
một khối dữ liệu đƣa vào mạng đƣợc chế thành các gói và đƣợc gửi đi tại từng thời điểm,
mỗi gói bao gồm dữ liệu cùng với địa chỉ và các thông số cần thiết, các gói không phải là
file.
Trong mạng chuyển mạch gói có 2 cách truyền gói đƣợc dùng: Datagram và Virtual
Circuit
1. DATAGRAM: các gói là độc lập giống nhƣ trong chuyển mạch thông báo, các
thông báo độc lập nhau. Cách truyền nhƣ vậy, mỗi gói độc lập đƣờng đi có thể không
giống nhau gọi là DATAGRAM (DG)
2. MẠCH ẢO (Virtual Circuit): Trong mạch ảo sự nối logic mạch đƣợc thiết lập
trƣớc khi truyền mỗi gói, mỗi gói bây giờ gồm cả nhận dạng VC và dữ liệu. Mỗi Node
với con đƣờng đã định biết đƣợc cần phải truyền gói trực tiếp đến đâu không cần phải tìm
đƣờng nữa. Một trong 2 trạm sẽ chấm dứt kết nối bằng cách truyền gói CLEAR
REQUEST
Cùng một thời gian một trạm có thể có nhiều VC đến một trạm khác và có thể có nhiều
VC đến nhiều trạm khác. Nhƣ vậy tính chất cơ bản của VC là đƣờng nối logic giữa 2 trạm
đƣợc thiết lập trƣớc khi truyền dữ liệu , điều đó không có nghĩa là có một con đƣờng cụ
thể nhƣ trong chuyển mạch kênh. Gói đƣợc giữ ở một node và sắp hàng để đƣợc đƣa ra
trên đƣờng nối. Chỗ khác với DATAGRAM là trong VC NODE không cần tìm đƣờng
cho mỗi gói mà nó chỉ làm một lần cho một lần nối.
Chú ý: Nếu một Node bị hƣ tất cả các VC qua Node đều bỏ, còn với DG nếu node đó bị
hƣ thì gói tìm con đƣờng khác.
Những điều chính yếu của mạng chuyển mạch gói là:
Routing: Chức năng đầu tiên của PS là nhận những gói từ trạm nguồn và cung cấp
nó đến ngƣời nhận, để hoàn thành việc đó, một hoặc nhiều con đƣờng thông qua mạng
đƣợc chọn, thông thƣờng khả năng cho phép nhiều hơn 1. Điều đó có nghĩa là con đƣờng
đƣợc chọn cần phải đảm bảo một số yêu cầu cần thiết trong chức năng đƣờng truyền nhƣ
chính xác , đơn giản, ổn định hợp lý tối ƣu.
Sự chọn đƣờng dựa vào tiêu chuẩn đơn giản là chọn đƣờng ngắn nhất ( một đƣờng với
TS. NGUYỄN VĂN VINH
-11-
MẠNG THÔNG TIN
KHOA ĐIỆN-ĐIỆN TỬ
ĐHSP KT HƯNG YÊN
node ít nhất ) thông qua mạng. Thực tế là ngƣời ta thƣờng dùng các con đƣờng có thời
gian đi là nhỏ nhất, Nhƣng không phải khi nào con đƣờng đi có thời gian nhỏ nhất cũng
là con đƣờng ngắn nhất. Giá trị nhỏ nhất bao gồm cho từng đƣờng và đƣờng thông qua
mạng bao gồm tích luỹ giá trị bé nhất của các đƣờng thành phần, Những điểm cần quyết
định khi lựa chọn gồm:
- Sự quyết định về thời gian
- Sự quyết định về vị trí
- Routing phân tán
- Routinh tập trung
Một trong những cách tìm đƣờng đơn giản là tìm đƣờng cố định. Trong trƣờng hợp đó,
một con đƣờng đƣợc xác định cho một cặp nguồn. Một thƣ mục tìm đƣờng tại trung tâm
đƣợc tạo nên. thƣ mục cho ta Node nguồn Node đích và node lân cận phải qua. Thƣ mục
đƣợc lƣu lại ở bộ điều khiển trung tâm mạng.
Một kỹ thuật tìm đƣờng đơn giản khác là tìm đƣờng động, Kỹ thuật này không yêu cầu
bất kỳ thông tin nào của mạng và nó làm việc nhƣ sau:
Gói gửi từ một nguồn đến mọi Node lân cận. ở tại mỗi node đến, gói vừa mới đến lại
chuyển đi trên trên mọi đƣờng ra, ngoài đƣờng nó đến, và cứ tiếp tục nhƣ vậy
Trafic control là giá trị lƣu lƣợng trong mạng cần phải điều hoà để tăng hiệu suất và
ổn định công suất. các phần tử của Traffic control..Traffic control có 4 loại với mục đích
khác nhau: Flowcontrol, Congestion control, Deadlock control.
Flow control liên quan đến việc điều chỉnh lƣu lƣợng của dữ liệu truyền giữa 2
điểm, cơ sở của Flow control là cho phép bộ thu với lƣu lƣợng sao cho không bị tràn.
Điển hình của Flow control là thực hiện với một số loại kỹ thuật nhƣ cửa sổ trƣợt
Congestion control là kiểm tra sự nghẽn mục đích là nắm đƣợc số của packet đƣợc
đƣa vào mạng theo mức. Mạng chuyển mạch gói là là một mạng xếp hàng tại mỗi Node,
các gói đƣợc xếp hàng để dƣa ra theo một đƣờng ra nào đó, nếu nhƣ số lƣợng các gói đến
xếp hàng nhiều hơn nhiều hơn lƣợng các gói có thể truyền thì độ lớn của hàng càng phình
ra, còn nếu nhƣ lƣợng các gói đến (tốc độ) ít hơn lƣợng gửi đi thì vấn dề xếp hàng không
xảy ra và tốc độ đến bằng tốc độ truyền đi. Trên mỗi đƣờng có các gói đến hoặc đi. Ta có
thể giả thiết rằng có 2 buffer cho mỗi đƣờng 1 dành cho các gói đến và 1 dành cho gói
xếp hàng chuyển đi.
Trong trƣờng hợp, gói đến nó đƣợc lƣu lại ở bộ nhớ đệm đến của đƣờng dây tƣơng ứng,
Node kiểm tra gói đến và quyết định đƣờng đi và chuyển gói đó đến buffer ra thích hợp.
gói đƣợc xếp hàng chờ đƣa ra với khả năng nhanh nhất, Nếu nhƣ gói đến quá nhanh so
TS. NGUYỄN VĂN VINH
-12-
MẠNG THÔNG TIN
KHOA ĐIỆN-ĐIỆN TỬ
ĐHSP KT HƯNG YÊN
với hoạt động của Node hoặc quá nhanh so với việc xoá trong bộ nhớ đệm ra thì đƣơng
nhiên gói sẽ đến mà không đƣợc giữ lại và làm cho đƣờng truyền bị nghẽn.
Deadlock control Một Node không chấp nhận chuyển tiếp các gói vì nó không có
buffer để dùng
Error control chức năng cuối cùng của chuyển mạch gói là kiểm tra sai có nhiều
nguyên nhân dẫn đến sai, mất gói trong chuyển mạch gói đó là: Đƣờng nối hƣ, Node hƣ,
Trạm thu nhận hƣ
1.5. Chuẩn hóa mô hình tham chiếu OSI (Open System Interconnection)
1.5.1 Kiến trúc phân tầng
Để giảm độ phức tạp khi thiết kế và cài đặt mạng số liệu đƣợc thiết kế theo quan
điểm kiến trúc 7 tầng nguyên tắc là: mỗi hệ thống trong một mạng đều có số lƣợng tầng là
7 chức năng của mỗi tầng là nhƣ nhau, xác định giao diện giữa 2 tầng kề nhau và giao
thức giữa 2 tầng đồng mức của 2 hệ thống kết nối với nhau.
Trên thực tế dữ liệu không đƣợc truyền trực tiếp từ tầng thứ i của hệ thống này sang
tầng thứ i của hệ thống kia (trừ tầng thấp nhất trực tiếp sử dụng đƣờng truyền vật lý). Từ
hệ thống gửi truyền sang hệ thống nhận theo quy trình nhƣ sau:
Dữ liệu từ tầng i của hệ thống gửi sẽ đi từ tầng trên xuống tầng dƣới và tiếp tục đến
tầng dƣới cùng – tầng vật lý qua đƣờng truyền vật lý chuyển đến hệ thống nhận và dữ
liệu sẽ đi ngƣợc lên các tầng trên đến tầng đồng mức thứ i. Nhƣ vậy 2 hệ thống kết nối
với nhau chỉ có tầng vật lý mới có kết nối vật lý còn các tầng khác chỉ có kết nối logic
1.5.2 Mô hình tham chiếu
Mô hình OSI đƣợc hình thành vào năm 1974 bởi hội đồng các tiêu chuẩn đƣợc biết
nhƣ tổ chức các tiêu chuẩn quốc tế (ISO). Mô hình này, nhƣ là mô hình liên kết các hệ
thống mở, hoặc mô hình OSI, phân chia hệ thống thông tin thành 7 lớp. Mỗi lớp thực
hiện một chức năng riêng biệt nhƣ một phần công việc để cho phép các chƣơng trình ứng
dụng trên các hệ thống khác liên lạc, nếu nhƣ chúng đang hoạt động trên cùng một hệ
thống.
Mô hình OSI là một mô hình kiến trúc cơ bản. Mô hình không dành riêng cho phần
mềm hoặc phần cứng nào. OSI miêu tả các chức năng của mỗi lớp nhƣng không cung cấp
phần mềm hoặc thiết kế phần cứng để phục vụ cho mô hình này. Mục đích sau cùng của
mô hình là cho khả năng hoạt động tƣơng lai của nhiều thiết bị truyền thông.
Một thiết bị truyền thông có thể đƣợc thiết kế dựa trên mô hình này. Thông qua việc
đề cập nhiều lần bởi các qui định của LAN, có một số dữ liệu và thông tin thoại đƣợc thiết
kế theo mô hình OSI.
TS. NGUYỄN VĂN VINH
-13-
MẠNG THÔNG TIN
KHOA ĐIỆN-ĐIỆN TỬ
ĐHSP KT HƯNG YÊN
Có 7 và chỉ 7 lớp tạo lên mô hình này (việc qui định các mức và các lớp có thể đƣợc
sử dụng, hình 1.6 mô tả các lớp theo trình tự từ dƣới lên trên; Lớp vật lý (physical layer),
lớp liên kết dữ liệu Data link layer), lớp mạng (Network layer), lớp vận chuyển (Transport
layer), lớp tập hợp (Session layer), lớp trình bầy (presentation) và lớp ứng dụng
(application layer). Mỗi lớp có một mục đích riêng và có chức năng độc lập của chúng.
Application
Presentation
Ứng dụng
Trình bày
Session
Phiên
Vận chuyển
Mạng
Transport
Network
Datalink
Liên kết dữ liệu
Vật lý
Physical
Hình 1.6. Mô hình OSI
Physical layer: Lớp này định nghĩa các phƣơng pháp sử dụng để truyền và thu dữ
liệu trên mạng, nó bao gồm: cáp, các thiết bị đƣợc sử dụng để kết nối bộ giao tiếp mạng
của trạm tới cáp.
Tín hiệu liên quan tới dữ liệu truyền/thu và khả năng xác định các lối dữ liệu trê
phƣơng tiện mạng ( the cable plant).
Datalink layer: lớp này đồng bộ hoá truyền dẫn và vận dụng điều khiển lối vào mức
khung và phục hồi thông tin có thể truyền trên lớp vật lí. Khuôn dạng khung và CRC
(kiểm tra vòng) đƣợc thực hiện tại các lớp vật lý. Lớp này thực hiện các phƣơng pháp truy
nhập nhƣ Ethernet và Token Ring. Nó luôn cung cấp địa chỉ lớp vật lí cho khung truyền.
Network layer: Lớp này điều khiển việc chuyển tiếp các thông báo giữa các trạm.
Trên cơ sở một số thông tin, lớp này sẽ cho phép dữ liệu theo trình tự giữa hai trạm để
hạn chế cho cả hai đƣờng logic và vật lí. Lớp này cho phép các khối dữ liệu đƣợc truyền
tới các mạng khác thông qua việc sử dụng một số thiết bị đƣợc biết nhƣ router. Qua các
router đƣợc định nghĩa tại lớp này.
Transport layer: Lớp này cung cấp cho truyền dẫn end-to-end của dữ liệu ( trạm
nguồn tới trạm đích). Nó cho phép dữ liệu đƣợc truyền một cách tin cậy, và đảm bảo rằng
TS. NGUYỄN VĂN VINH
-14-
MẠNG THÔNG TIN
KHOA ĐIỆN-ĐIỆN TỬ
ĐHSP KT HƯNG YÊN
dữ liệu đƣợc truyền hoặc đƣợc thu không có lỗi, chính xác theo trình tự.
Session layer: Lớp này thiết lập, duy trì và cắt đứt liên kết giữa hai trạm trên một
mạng. Lớp này chịu trách nhiệm biên dịch địa chỉ tên trạm.
Presentation layer: Lớp này thực hiện chuyển đổi cú pháp dữ liệu để đáp ứng yêu
cầu truyền dữ liệu của các ứng dụng qua môi trƣờng OSI.
Application layer: Lớp này đƣợc sử dụng cho các ứng dụng, đó là yếu tố để thực
hiện trên mạng. Các ứng dụng nhƣ truyền file, thƣ điện tử ...
Trên đây là những gì mà mô hình OSI đã thực hiện. Ngay sau khi mô hình OSI này
ra đời thì nó đƣợc dùng làm có sở để nối các hệ thống mở phục vụ cho các ứng dụng phân
tán. Từ “mở” ở đây nói lên khả năng hai hệ thống có thể kết nối để trao đổi thông tin với
nhau, nếu chúng tuân thủ theo mô hình tham chiến và các chuẩn liên quan.
Điều quan trọng nhất của mô hình OSI là đƣa ra các giải pháp cho vấn đề truyền
thông giữa các trạm không giống nhau. Hai hệ thống dù khác nhau nhƣ thế nào đều có thể
truyền thông với nhau nếu chúng bảo đảm những điều kiện sau:
Chúng cài đặt cùng một tập các chức năng truyền thông.
- Các chức năng đó đƣợc tổ chức thành một tập các tầng, các tầng đồng mức phải
cung cấp các chức năng nhƣ nhau
- Các tầng đồng mức phải sử dụng một giao thức chung
Để bảo đảm bảo các điều kiện trên cần phải có các chuẩn. Các chuẩn phải xác định
các chức năng và dịch vụ của tầng. Các chuẩn cũng phải xác định các giao thức giữa các
tầng đồng mức. Mô hình OSI 7 lớp chính là cơ sở để xây dựng các chuẩn đó.
1.5.3. Phương thức hoạt động
Ơ mỗi tầng trong mô hình OSI có 2 phƣơng thức hoạt động: phƣơng thức có liên kết
(connection oriented) và phƣơng thức không liên kết (connectionless)
Với phƣơng thức có liên kết trƣớc khi truyền dữ liệu cần thiết lập một liên lết logic
giữa các thực thể đồng mức. nhƣ vậy quá trình truyền thông gồm 3 giai đoạn:
- Thiết lập liên kết logic: 2 thực thể đồng mức ở 2 hệ thống sẽ thƣơng lƣợng với
nhau về các thông số sẽ sử dụng trong giai đoạn sau
- Truyền dữ liệu : Dữ liệu sẽ đƣợc truyền với cơ chế kiểm soát và quản lý kèm theo
(nhƣ kiểm soát lỗi , kiểm soát luồng, cắt/hợp dữ liệu)
- Huỷ bỏ liên kết : giải phóng các tài nguyên hệ thống đã đƣợc cấp phát cho liên kết
để dùng cho các liên kết khác
Mỗi giai đoạn trên thƣờng đƣợc thể hiện bằng một hàm tƣơng ứng. Thí dụ hàm
connect thể hiện giai đoạn thiết lập liên kết, hàm Data thể hiện giai đoạn truyền dữ liệu và
TS. NGUYỄN VĂN VINH
-15-
MẠNG THÔNG TIN
KHOA ĐIỆN-ĐIỆN TỬ
ĐHSP KT HƯNG YÊN
hàm Disconnect thể hiện giai đoạn huỷ bỏ liên kết. Cùng với 4 hàm nguyên thuỷ trên cho
mỗi giai đoạn ta sẽ có 12 thủ tục chính để xây dựng các dịch vụ và các giao thức chuẩn
theo kiểu OSI.
Còn đối với phƣơng thức không liên kết thì không cần thiết lập liên kết logic và mỗi
đơn vị dữ liệu đƣợc truyền độc lập với các đơn vị dữ liệu trƣớc hoặc sau nó. Phƣơng thức
này chỉ có duy nhất một giai đoạn truyền dữ liệu
So sánh 2 phƣơng thức hoạt động trên thi phƣơng thức có liên kết cho phép truyền
dữ liệu tin cậy, do đƣợc kiểm soát và quản lý chặt chẽ theo từng liên kết lôgic, nhƣng cài
đặt khó khăn .
Phƣơng thức không liên kết cho phép các PDU có thể đƣợc truyền đi theo nhiều
đƣờng khác nhau để tới đích, thích nghi đƣợc với sự thay đổi trạng thái của mạng, nhƣng
lại gặp phải khó khăn khi tập hợp lại các PDU để chuyển tới ngƣời dùng. Về nguyên tắc 2
tầng lân cận không nhất thiết phải dùng chung một phƣơng thức hoạt động.
TS. NGUYỄN VĂN VINH
-16-
MẠNG THÔNG TIN
KHOA ĐIỆN-ĐIỆN TỬ
ĐHSP KT HƯNG YÊN
Chƣơng 2. ĐỊNH TUYẾN TRONG MẠNG THÔNG TIN
2.1. YÊU CẦU VỀ ĐỊNH TUYẾN TRONG MẠNG THÔNG TIN
Phần này giới thiệu các thuật ngữ và các khái niệm cơ bản nhằm mô tả các mạng, graph, và
các thuộc tính của nó. Lý thuyết graph là một môn học xuất hiện từ lâu, nhƣng lý thuyết này
có một số thuật ngữ đƣợc chấp nhận khác nhau dùng cho các khái niệm cơ bản. Vì thế có thể
sử dụng một số thuật ngữ khác nhau để lập mô hình graph cho mạng. Các thuật ngữ đƣợc
trình bày dƣới đây này là các thuật ngữ đã đƣợc công nhận và đƣợc sử dụng thƣờng xuyên
chƣơng này.
Một graph G, đƣợc định nghiã bởi tập hợp các đỉnh V và tập hợp các cạnh E. Các đỉnh thƣờng
đƣợc gọi là các nút và chúng biểu diễn vị trí (ví dụ một điểm chứa lƣu lƣợng hoặc một khu
vực chứa thiết bị truyền thông). Các cạnh đƣợc gọi là các liên kết và chúng biểu diễn phƣơng
tiện truyền thông. Graph có thể đƣợc biểu diễn nhƣ sau:
G=(V, E)
Hình 2.1 là một ví dụ của một graph.
Hình 2.1. Một graph đơn giản
Mặc dù theo lý thuyết, V có thể là tập hợp rỗng hoặc không xác định, nhƣng thông thƣờng V là
tập hợp xác định khác rỗng, nghĩa là có thể biểu diễn
V={vi | i=1,2,......N}
trong đó N là số lƣợng nút. Tƣơng tự E đƣợc biểu diễn:
E={ei | i=1,2,......M}
Một liênkết, ej, tƣơng ứng một kết nối giữa một cặp nút. Có thể biểu diễn một liên kết ej giữa
nút i và k bởi
ej=(vi,vk)
hoặc bởi
ej=(i,k)
TS. NGUYỄN VĂN VINH
-17-
MẠNG THÔNG TIN
KHOA ĐIỆN-ĐIỆN TỬ
ĐHSP KT HƯNG YÊN
Một liênkết gọi là đi tới một nút nếu nút đó là một trong hai điểm cuối của liên kết. Nút i và
k gọi là kề nhau nếu tồn tại một liên kết (i, k) giữa chúng. Những nút nhƣ vậy đƣợc xem là
các nút láng giềng. Bậc của nút là số lƣợng liên kết đi tới nút hay là số lƣợng nút láng giềng.
Hai khái niệm trên là tƣơng đƣơng nhau trong các graph thông thƣờng. Tuy nhiên với các
graph có nhiều hơn một liên kết giữa cùng một cặp nút, thì hai khái niệm trên là không tƣơng
đƣơng. Trong trƣờng hợp đó, bậc của một nút đƣợc định nghĩa là số lƣợng liên kết đi tới nút
đó.
Một liênkết có thể có hai hƣớng. Khi đó thứ tự của các nút là không có ý nghiă. Ngƣợc lại thứ
tự các nút có ý nghĩa. Trong trƣờng hợp thứ tự các nút có ý nghĩa, một liên kết có thể đƣợc
xem nhƣ là một cung và đƣợc định nghĩa
aj=[vi,vk]
hoặc đơn giản hơn
aj=[i,k]
ở đây k đƣợc gọi là cận kề hƣớng ra đối với i nếu một cung [i,k] tồntại và bậchướng ra củai
là số lƣợng các cung nhƣ vậy. Khái niệm cận kề hƣớng vào và bậc cận kề hƣớng vào cũng
đƣợc định nghĩa tƣơng tự.
Một graph gọi là một mạng nếu các liênkết và các nút có mặt trong liên kết có các thuộc tính
(chẳng hạn nhƣ độ dài, dung lƣợng, loại...). Các mạng đƣợc sử dụng để mô hình các vấn đề
cần quan tâm trongtruyền thông, các thuộc tính riêng biệt của nút và liên kết thì liên quan đến
các vấn đề cụ thể trong truyền thông.
Sự khác nhau giữa các liên kết và các cung là rất quan trọng cả về việc lập mô hình cho mạng
lẫn quá trình hoạt động bên trong của các thuật toán, vì vậy sự khác nhau cần phải luôn đƣợc
phân biệt rõ ràng. Về mặt hình học các liênkết làcác đƣờng thẳng kết nối các cặp nút còn các
cung là các đƣờng thẳng có mũi tên ở một đầu, biểu diễn chiều của cung.
Một graph có các liên kết gọi là graph vô hƣớng, tuy nhiên một graph có các cung gọi là
graph hữu hƣớng. Một graph hữu hƣớng có thể có cả các liên kết vô hƣớng. Thông thƣờng ,
các graph đƣợc giả sử là vô hƣớng, hoặc sự phân biệt đó là không có ý nghĩa.
Có thể có khả năng xảy ra hiện tƣợng xuất hiện nhiều hơn một liên kết giữa cùng một cặp nút
(điều này tƣơng ứng với việc có nhiều kênh thông tin giữa hai chuyển mạch). Những liên kết
nhƣ vậy đƣợc gọi là các liên kết song song. Một graph có liên kết song song gọi là một
multigraph.
Cũng có khả năng xuất hiện các liên kết giữa một nút nào đó và chính nút đó. Những liên kết
đó đƣợc gọi là các self loop. Chúng ít khi xuất hiện và thƣờng xuất hiện do việc xem hai nút
nhƣ là một nút trong quá trình lập mô hình graph cho một mạng hoặc phát sinh trong quá trình
TS. NGUYỄN VĂN VINH
-18-
MẠNG THÔNG TIN
KHOA ĐIỆN-ĐIỆN TỬ
ĐHSP KT HƯNG YÊN
thực hiện một thuật toán có việc hợp nhất các nút. Hình 4.2 minh hoạ một graph có các liên
kết song songvà các self loop. Một graph không có các liên kết song song hoặc các self loop
gọi là một graph đơn giản. Việc biểu diễn và vận dụng các graph đơn giản là tƣơng đối dễ
dàng, vì vậy giả thiết rằng các graph đƣợc xem xét là các graph đơn giản. Nếu có sự khác biệt
với giả thiết này, chúng sẽ đƣợc chỉ ra.
2.2. CÁC MÔ HÌNH ĐỊNH TUYẾN QUẢNG BÁ (broadcast routing)
2.2.1 Lan tràngói (flooding)
Một dạng mạnh hơn của định tuyến riêng biệt đó là lan tràn gói. Trong phƣơng thức này, mỗi
gói đi đếnrouter sẽ đƣợc gửi đi trêntất cả các đƣờng ra trừ đƣờng mà nó đi đến. Phƣơng thức
lan tràn gói này hiển nhiênlà tạo ra rất nhiềugói sao chép(duplicate). Trên thực tế, số gói này
là không xác định trừ khi thực hiện một số biện pháp để hạn chế quá trình này.
Một trong những biện pháp đó là sử dụng bộ đếm bƣớc nhảy trong phần tiêu đề của mỗi gói.
Giá trị này sẽ bị giảm đi một tại mỗi bƣớc nhảy. Gói sẽ bị loại bỏ khi bộ đếm đạt giá trị không.
Về mặt lý tƣởng, bộ đếm bƣớc nhảy sẽ có giá trị ban đầu tƣơng ứng với độ dài từ nguồn đến
đích. Nếu nhƣ ngƣời gửi không biết độ dài của đƣờng đi, nó có thể đặt giá trị ban đầu của bộ
đếm cho trƣờng hợp xấu nhất. Khi đó giá trị ban đầu đó sẽ đƣợc đặt bằng đƣờng kính của
mạng con.
Một kỹ thuật khác để ngăn sự lan tràngói là thêm số thứ tự vào tiêu đề các gói. Mỗi router sẽ
cần có một danh sach theo nút nguồn để chỉ ra những số thứ tự từ nguồn đó đã đƣợc xem xét.
Để tránh danh sách phát triển không giới hạn, mỗi danh sách sẽ tăng lên bởi số đếm k để chỉ
ra rằng tất cảcác số thứ tự đến k đã đƣợc xem. Khi một gói đi tới, rất dễ dàng có thể kiểm tra
đƣợc gói là bản sao hay không. Nếu đúng gói là bản sao thì gói này sẽ bị loại bỏ.
Lan tràn gói có ƣu điểm làlan tràn gói luôn luôn chọn đƣờng ngắn nhất. Có đƣợc ƣu điểm này
là do về phƣơng diện lý thuyết nó chọn tất cả các đƣờng có thể do đó nó sẽ chọn đƣợc đƣờng
ngắn nhất. Tuy nhiên nhƣợc điểm của nó là số lƣợng gói gửi trong mạng quá nhiều.
Sử dụng lan tràn gói trong hầu hết các ứng dụng là không thực tế. Tuy vậy lan tràn gói có thể
sử dụng trong những ứng dụng sau.
- Trong ứng dụng quân sự, mạng sử dụng phƣơng thức lan tràn gói để giữ cho mạng luôn
luôn hoạt động tốt khi đối mặt với quân địch.
- Trong những ứng dụng cơ sở dữ liệuphân bố, đôi khi cần thiết phải cập nhật tất cả cơ sở dữ
liệu. Trong trƣờng hợp đó sử dụng lan tràn gói là cần thiết. Ví dụ sự dụng lan tràn gói để gửi
cập nhật bản định tuyến bởi vì cập nhật không dựa trên độ chính xác của bảng định tuyến.
TS. NGUYỄN VĂN VINH
-19-
MẠNG THÔNG TIN
KHOA ĐIỆN-ĐIỆN TỬ
ĐHSP KT HƯNG YÊN
- Phƣơng pháp lan tràn gói có thể đƣợc dùng nhƣ là đơn vị để so sánh phƣơng thức định
tuyến khác. Lan tràn gói luôn luôn chọn đƣờng ngắn nhất. Điều đó dẫn đến không có giải
thuật nào có thể tìm đƣợc độ trễ ngắn hơn.
Một biến đổi của phƣơng pháp lan tràn gói là lan tràn gói có chọn lọc. Trong giải thuật này,
router chỉ gửi gói đi ra trên các đƣờng mà đi theo hƣớng đích. Điều đó có nghĩa là không gửi
gói đến những đƣờng mà rõ rang nằm trên hƣớng sai.
2.2.2 Định tuyến bước ngẫunhiên (random walk)
Trong phƣơng pháp định tuyến này, router sẽ chuyển gói đi đến trên một đƣờng đầu ra đƣợc
chọn một cách ngẫu nhiên. Mục tiêu của phƣơng pháp này là các gói lang thang trong mạng
cuối cùng cũng đến đích. Với phƣơng pháp này giúp cho quá trình cân bằng tải giữa các
đƣờng. Cũng giống nhƣ phƣơng pháp định tuyến lan tràn gói, phƣơng pháp này luôn đảm bảo
là gói cuối cùng sẽ đến đích. So với phƣơng pháp trƣớc thì sự nhân rộng gói trong mạng sẽ ít
hơn. Nhƣợc điểm của phƣơng pháp này là đƣờng từ nguồn đến đích có thể dài hơn đƣờng
ngắn nhất. Do đó trễ đƣờng truyền sẽ dài hơn sẽ trễ ngắn nhất thực sự tồn tại trong mạng.
2.2.3 Định tuyến khoai tâynóng (hot potato)
Định tuyến riêng biệt là loại định tuyến mà router quyết định tuyến đi chỉ dựa vào thông tin
bản thân nó lƣợm lặt đƣợc.
Đây là một thuật toán tƣơng thích riêng biệt (isolated adaptive algorithm). Khi một gói đến
một nút, router sẽ cố gắng chuyển gói đó đi càng nhanh càng tốt bằng cách cho nó vào hàng
chờ đầu rangắn nhất. Nói cách khác, khi có gói đi đếnrouter sẽ tínhtoánsố gói đƣợc nằm chờ
để truyền tren mỗi đƣờng đầu ra. Sau đó nó sẽ gán gói mới vào cuối hàng chờ ngắn nhất mà
router tại một thời điểm nào đó. Có ba hàng chờ đầu ra tƣơng ứng với 03 đƣờng ra. Các gói
đang xếp hàng trên mỗi đƣờng để chờ đƣợc truyền đi. Trong ví dụ ở đây, hàng chờ đến F là
hàng chờ ngắn nhất với chỉ có một gói nằm trên hàng chờ này. Giảu thuật khoai tây nóng do
đó sẽ đặt gói mới đến vào hàng chờ này.
TS. NGUYỄN VĂN VINH
-20-
MẠNG THÔNG TIN
KHOA ĐIỆN-ĐIỆN TỬ
ĐHSP KT HƯNG YÊN
Hình 2.1. Hàng chờ bên trong router
Có thể biến đổi ý tƣởng này một chút bằng cách kết hợp định tuyến tĩnh với giải thuật khoai
tây nóng. Khi gói đi đến, router sẽ tính đến cả những trọng số tĩnh của đƣờng dây và độ dài
hàng chờ. Một khả năng là sử dụng lựa chọn tĩnh tốt nhất trừ khi độ dài hàng chờ lớn hơn một
ngƣỡng nào đó. Một khả năng khác là sử dụng độ dài hàng chờ ngắn nhất trừ trọng số tĩnh của
nó là quá thấp. Còn một cáchkhác là sắp xếp các đƣờng theo trọngsố tĩnhcủa nó và sau đó lại
sắp xếp theo độ dài hàng chờ của nó. Sau đó sẽ chọn đƣờng có tổng vị trí sắp xếp là nhỏ nhất.
Dù giải thuật nào đƣợc chọn đi chăng nữa cũng có đặc tính là khi ít tải thì đƣờng có trọng số
cao nhất sẽ đƣợc chọn, nhƣng sẽ làm cho hàng chờ cho đƣờngnày tăng lên. Sau đó một số lƣu
lƣợng sẽ đƣợc chuyển sang đƣờng ít tải hơn.
2.2.4 Định tuyến nguồn (source routing) và môhình cây(spanning tree)
Chúng ta sẽ xét một số thuật toán cơ bản dùng cho việc tìm kiếm các cây đƣợc sử dụng để
thiết kế và phân tích mạng. Một cây là một graph không có các vòng; bất kỳ một cặp nút nào
cũng chỉ có duy nhất một đƣờng đi. ở đây chủ yếu xem xét các graph vô hƣớng, những graph
đó có các liên kết đƣợc sử dụng cả hai chiều trong quá trình tạo ra các đƣờng đi.
Vì một số lý do, các cây rất hữu dụng và đƣợc sử dụng nhƣ là graph cơ bản cho các thuật toán
và các kỹ thuật phân tích và thiết kế mạng. Thứ nhất, các cây là mạng tối thiểu; cung cấp một
sự kết nối mà không một liên kết nào là không cần thiết. Thứ hai, do việc chỉ cung cấp duy
nhất một đƣờng đi giữa một cặp nút bất kỳ, các cây giải quyết các vần đề về định tuyến (nghĩa
là quyết định việc chuyển lƣu lƣợng giữa hai nút). Điều đó làm đơn giản mạng và dạng của
nó. Tuy nhiên, vì các cây liên thông tối thiểu nên cũng đơn giản và có độ tin cậy tối thiểu. Đó
là nguyên nhân tại sao các mạng thực tế thƣờng có tính liên thông cao hơn. Chính vì vậy, việc
thiết kế một mạng thƣờng bắt đầu bằng một cây.
2.2.5 Duyệt cây
Cho trƣớc một cây nào đó, chúng ta có thể đi tới mọi nút của nó. Quá trình đó gọi là một quá
trình duyệt cây. Trong quá trình thực hiện, các cạnh trong cây đƣợc duyệt hai lần, mỗi lần
theo một hƣớng khác nhau. Có nhiều cách duyệt khác nhau. Đầu tiên, chỉ ra một nút của cây
làm nút gốc. Việc duyệt đƣợc thực hiện xoay quanh nút đó. Có một số điều kiện để lựa chọn
nút gốc này (chẳng hạn nút gốc là một khu vực máy tính trung tâm). Ngoài ra, nút gốc có thể
đƣợc chọn một cách ngẫu nhiên.
Giả sử nút A trong hình 4.1 là nút gốc của cây. Từ A chúng ta có thể lần lƣợt đi tới các nút kề
cận của nó nhƣ là B, C hoặc D. Sau đó, lại đi theo các nút kề cận của chúng (B, C và D) là E,
F, G và H. Tiếp tục đi tới lần lƣợt các nút kề cận khác bên cạnh các nút này. Khi đó, việc
duyệt này sẽ kết thúc khi tới các nút I, J, K và L. Quá trình này đƣợc gọi là tìm kiếm theo
TS. NGUYỄN VĂN VINH
-21-
MẠNG THÔNG TIN
Tải về để xem bản đầy đủ
121 trang
12/01/2024
11521
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Mạng thông tin", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_mang_thong_tin.pdf
