Chơng I : Mở BàI
Sự xuất hiện của mạng máy tính vào những năm đầu của thập kỉ 60 đánh
dấu một bớc phát triển vợt bậc về Công Nghệ Thông Tin (CNTT) trong xã
hội loài ngời. Cùng với thời gian sự kết hợp giữa máy tính và các hệ thống
truyền thông,mà cụ thể là viễn thông, một cách ngày càng hoàn hảo hơn đã
đem lại một chuyển biến có tính chất cách mạng trong vấn đề khai thác và sử
dụng hệ thống máy tính. Chính vì thế mà giờ đây chúng ta có thể :
- Chia sẽ tài nguyên mạng
- Dùng chung các thiết bị mạng nh: các ổ đĩa, máy in, modem
- Sử dụng các dịch vụ mạng nh: các trình duyệt web, mail, chat
- Tham gia hội thảo trực tuyến
- Phát triển hệ thống thơng mại điện tử
Tuy nhiên khi thiết kế, các nhà thiết kế tự do lựa chọn kiến trúc mạng
riêng của mình. Từ đó dẫn đến tình trạng không tơng thích giữa các mạng:
phơng pháp truy nhập đờng truyền khác nhau, sử dụng họ giao thức khác
nhau sự không tơng thích đó làm trở ngại cho sự tơng tác của ngời sử dụng
các mạng khác nhau. Nhu cầu trao đổi thông tin càng lớn thì trở ngại đó càng
không thể chấp nhận dợc đối với ngời sử dụng. Sự thúc bách của khách hàng
dã khiến cho các nhà sản xuất và các nhà nghiên cứu, thông qua các tổ chức
chuẩn hoá quốc gia và quốc tế tích cực tìm kiếm một sự hội tụ cho các sản
phẩm mạng trên thị trờng. Để có đợc điều đó, trớc hết cần xây dựng đợc một
khung chuẩn về kiến trúc mạng để làm căn cứ cho các nhà thiết kế và chế tạo
các sản phẩm về mạng.
Vì lý do đó, tổ chức tiêu chuẩn hoá quốc tế (International organization for
standardization viết tắt là ISO ) đã lập ra (1997) một tiểu ban nhằm phát
triển một khung chuẩn nh thế. Kết quả là năm 1984, ISO đã xây dựng xong
mô hình tham chiếu cho việc nối kết hệ thống mở (Reference model for open
systems interconnection hay gọn hơn là OSI reference model). Mô hình này
đợc dùng làm cơ sở để nối kết 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ể nối kết để trao
đổi thông tin với nhau nếu chúng tuân thủ mô hình tham chiếu và các chuẩn

Giao thức tầng i
Giao thức tầng 1
Đờng truyền vật lý
Hình 1: kiến trúc phân tâng tổng quát
II. MÔ HìNH THAM CHIếU OSI
Từ sự phân tầng nói trên cho nên việc chuẩn hoá các mạng máy tính từ các
hãng khác nhau để chúng có thể truyền thông đợc với nhau là điều tất yếu.
Các tổ chức đI đầu trong việc chuẩn hoá nh :
International organization for standization(ISO) là tổ chức tiêu chuẩn hoá
quốc tế hoạt động dới sự bảo trợ của liên hợp quốc bao gồm các thành viên
của các cơ quan tiêu chuẩn hoá của nhiều quốc gia.ISO tổ chức thành các
ban kĩ thuật phụ trách nhiều lĩnh vực khác nhau của xử lý thông tin. Mổi tổ
chức lại chia thành nhiều tiểu ban, mổi tiểu ban gồm nhiều nhóm đảm nhận
các vấn đề chuyên sâu.
Commité consultative international pour télégraphe ét téléphone(CCITT)
là tổ chức t vấn quốc tế về điện tín và điện thoại. tổ chức này cũng hoạt động
dới sự bảo trợ của liên hợp quốc với các thành viên thuộc các cơ quan bu
chính viễn thông của các quốc gia hay t nhân. cách hoạt động giống ISO nh-
ng sản phẩm của nó không gọi là chuẩn mà gọi là khuyến nghị. Tổ chức này
ban hành khuyến nghị loại V liên quan đến các mạng truyền dữ liệu,
khuyến nghị loại X liên quan đến các mạng truyền dữ liệu công cộng và
loại I dành cho mạng CSDN. CCITT chuẩn hoá mạng sớm hơn ISO và sản
phẩm của nó đợc tổ chức ISO thừa nhận và ban hành nh chuẩn quốc tế
và ngợc lại các chuẩn của ISO cũng đợc CCITT thừa nhận và ban hành nh là
một khuyến nghị. Các khuyến nghị chuẩn của CCITT nh là
Tầng N
Tầng N-1
Tầng i+1
Tầng i
Tầng i-1

không ảnh hởng đến các tầng khác kế nó.
Tạo một tầng khi dữ liệu đợc xử lý một cách khác biệt.
Khi ta thay đổi chức năng và giao thức của các tầng thì không ảnh hởng đến
các tầng khác.
Mổi tầng có giao diện với các tầng trên và dới nó.
Khi cần thiết thì ta có thể chia các tầng thành các tầng con.
Có thể huỷ bỏ các tầng con khi cần thiết.
Tạo các tầng con cho phép giao diện với các tầng kề cận.
Trong thực tế khi nghiên cứu về mô hình OSI không phảI tất cả các mạng
đều phân tầng tơng ứng với mổi tầng trong số bảy tầng của mô hình OSI. Mô
hình này phục vụ cho nền công nghiệp máy tính nh là một điểm tham chiếu
khi chúng ta đề cập tới các cấp độ hay các tầng trong mạng.
Điều thú vị của mô hình OSI chính là nó hứa hẹn giảI pháp cho vấn đề
truyền thông giữa các máy tính là không giống nhau. Hai hệ thống dù khác
nhau thì nó cũng có thể truyền thông một cách hiệu quả nếu chúng cùng thực
hiện một số điều kiện chung nhất:
Chúng càI đặt cùng một tầng các chức năng truyêng thông.
Các chức năng này đợc tổ chức thành cùngmộ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 nhng phơng thức cung cấp không
nhất thiết phảI nh nhau.
Những tầng đồng mức phảI sử dụng giao thức chung.
Sau đây là kiến trúc phân tầng theo mô hình OSI:
Hệ thống A Hệ thốngB
Giao thức tâng 7
Giao thức tâng 6
Giao thức tâng5
Giao thức tầng4
Giao thức tâng 3
Giao thức tâng 2
Giao thức tâng 1

tin điều khiển.
Tầng N+1 Interface
Tầng N (N) entity
Interface
Tầng N-1
Prôtcol (N) entity SAP
Hình 3 : Quan niệm tầng theo mô hình OSI.
Tơng tác giữa các tầng kề nhau bằng bốn kiểu hàm nguyên thuỷ nh
sau:
Request (yêu cầu): là hàm nguyên thuỷ ngời sử dụng dịch vụ dùng để gọi
một chức năng.
Indication (chỉ báo): là hàm nguyên thuỷ mà nhà cung cấp dịch vụ dùng
để gọi một chức năng hay chỉ báo một chức năng đã đợc gọi ở một điểm truy
cập dịch vụ SAP.
Response (trả lời): là hàm nguyên thuỷ mà ngời sử dụng dịch vụ dùng để
hoàn tất một chức năng đã đợc gọi từ trớc bởi một hàm nguyên thuỷ
indication.
Confirm (Xác nhận): là hàm nguyên thuỷ mà ngời cung cấp dịch vụ dùng
để hoàn tất một chức năng đã đợc gọi từ trớc bởi hàm Request ngay tại điểm
truy cập dịch vụ đó.
Nguyên lý hoạt động của các hàm nguyên thuỷ:
Hệ thống A hệ thống B ngời sử dụng dịch vụ4
Tầng N
Tầng N-1 Tầng N-1
Tầng N
request confirm response indication
interface

1)SDU và trở thành (N-1)PDU. (N-1)PDU chuyển xuống N-2 sẽ trở thành
(N-2)SDU ta lại thêm (N-2)PCI sẽ trở thành (N-2)PDU.
5
Mối quan hệ giữa các đơn vị dữ liệu của các tầng trong một hệ thống
phát dữ liệu nh sau:
Tầng N+1 (N)PDU
Tầng N (N)PCI
(N)SDU
(N)PDU
Tầng N-1 (N-1)PCI
(N-1)SDU
(N-1)PDU
Hình 5 : Quan hệ hiữa các đơn vị dữ liệu
Bên hệ thống nhận quá trình sẽ diễn ra trình tự ngợc lại. khi qua mổi tầng
PCI tơng ứng của mổi tầng sẽ đợc tách ra khỏi PDU trớc khi dữ liệu đI lên
tầng trên.
Mối quan hệ giữa các đơn vị dữ liệu ở các tầng trong một hệ thống
nhận dữ liệu nh sau:
Tầng N+1 (N)PDU
Tầng N
(N)SDU

(N)PCI
(N)PDU
Tầng N-1
(N-1)SDU
(N-1)PCI
(N-1)PDU
Hình 6 : Quan hệ giữa các đơn vị dữ liệu ở các tầng kề nhau trong hệ
thống nhận dữ liệu.

Hai phơng thức hoạt động trên đều có u và nhợc điểm. Tuỳ thộc vào yêu
cầu về chất lợng, hiêu quả, độ tin cậy của việc truyền tin mà lựa chọn phơng
thức truyền tin thích hợp. Hai tầng kề nhau có thể sử dụng hai phơng thức
khác nhau hoặc cùng nhau.
Tầng vật lý
1.Vai trò và chức năng của tầng vật lý
Nh đã trình bày ở trên, tầng vật lý cung cấp các phơng tiện điện, cơ ,chức
năng, thủ tục để thiết lập,duy trì và giải phóng liên kết vật lý giữa các hệ
thống.
-Thuộc tính điện liên quan đến sự biểu diển các bít tức các mức điện thế và
tốc độ truyền bít.
-Thuộc tính cơ liên quan đến tính chất vật lý của giao diện với một đơng
truyền.
-Thuộc tính chức năng cung cấp các chức năng đợc thực hiện bởi cácphần
tứ của giao diện vật lý, giửa một hệ thống và đờng truyền.
-Thuộc tính thủ tục liên quan đến giao thức điều khiểnviệc truyền các xâu
bit qua đờng truyền vật lý.
Tầng vật lý là tâng thấp nhất giao diện với đờng truyền vật lý, khi dữ liệu từ
tầng liên kết dữ liệu truyền trực tiếp tới tầng vật lý thì sẽ không có PDU cho
tầng vật lý, nghĩa là không có PCI cho tầng vật lý mà dữ liệu đợc truyền đi
theo dòng bit. Đây là điển khác biệt giữa tầng vật lý với các tầng khác.
2. Môi trờng thực và môi trờng logic của tầng vật lý
Cáp đồng trục Cáp quang
A B
Modem Transducer

Hình 7 : Môi trờng thực
Giả sử hai hệ thống A và B là hai hệ thống mở đợc nối với nhau thông qua
một đoạn cáp đòng trục và một đoạn cáp quang. Modem có nhiện vụ chuyển
tính hiệu số từ hệ thống A thành tính hiệu tơng tự dể truyền trên cáp đồng

Hai chuẩn tơng ứng của CCITT và EIA nhằm định nghĩa giao diện tầng vật lý
giữa DTE và DCE.
-Về phơng diện cơ thì chuẩn này sử dụng đầu nối 25 chân nên ta phải dùng
cáp 25 sợi để nối DTE và DCE.
-Về phơng diện điện thì chuẩn này quy định các tín hiệu số nhị phân:
0 tơng ứng với mức điện thế nhỏ hơn -3V và 1 tơng ứng với mức điện thế lớn
hơn +3V. Tín hiệu qua giao diện này không vợt quá 20kb/s với khoảng cách
dới 15 m.
Trong chuẩn này có các mạch,mổi chiều có một mạch dữ liệu nên có thể
hoạt động phơng thức hoạt động hai chiêud đồng thời.Một dây đất đợc cách
ly bảo vệ còn lại làm việc nh là mạch trả lời cho cả hai mạch dữ liệu.
Một số mạch chuẩn trong chuẩn này nh sau:
Tên mạch Chức năng Hớng
Data signals
-transmitted data(BA)
Dữ liệu đợc tạo bởi DTE DTE-DCE
8
Thực
thể
tầng
vật lý
Thực
thể
tầng
vật lý
Thực
thể
tầng
vật lý
-received data(BB)

ringing trên kênh
Chỉ rằng DCE đang nhận một tín hiệu
sóng mang
Khẳng định khi có căn cứ để tin răng dữ
liệu nhận đợc đã bị lỗi
Khẳng định để chọn tốc độ dữ liệu
Khẳng định để chọn tốc đọ dữ liệu
Clocking signals, các chuyển đổi ON và
OFF xảy ra ở trung tâm mổi phần tử tín
hiệu
Clocking signals nh trên liên quan đến
mạch BA
Clocking signal nh trên liên quan đến
mạch BB
Nối với khung máy và có thể với đất bên
ngoài
Thiết lâp tiếp đất chung cho tất cả các
mạch
DCE-DTE
DTE-DCE
DCE-DTE
DCE-DTE
DTE-DCE
DCE-DTE
DCE-DTE
DCE-DTE
DTE-DCE
DCE-DTE
DTE-DCE
DCE-DTE

-indication(i)
-signal element timing(S)
-byte timing(b)
-Dùng để mang dữ liệu sử
dụng lẫn thông tin điều
khiển, phụ thuộc vào trạng
thái của C và I
-Nh T cho hớng ngợc lại
-cung cấp thông tin điều
khiển tới DCE
-Cung cấp các chỉ báo DTE
-Thực hiện đồng bộ bit
-thực hiện đồng bộ byte
DTE-DCE
DCE-DTE
DTE-DCE
DCE-DTE
DCE-DTE
DCE-DTE
Giống nh RS-232-C và RS-449 có mạch truyền theo cả hai chiều. Các mạch
ở đây có thể cung cấp cả dữ liệu ngời sử dụng lẫn thông tin điều khiển.
Nhoài ra còn có hai mạch khác là C và I tơng ứng cho mỗi chiều dành chỉ
thông tin điều khiển và trạng thái. Chúng không mang các dòng dữ liệu số
mà có thể là trạng thái ON hay OFF. X21 đợc định nghĩa cho chế độ truyền
đồng bộ nên có một mạch đồng bộ bít. X21 chấp nhận chế độ truyền cân
bằng và không cân bằng nên cũng có sự hạn chế về tốc độ và khoảng cách.
Trong một số trờng hợp thì chỉ có chế độ cân bằng đựơc sử dụng trên tất cả
các mạch. Tất cả các thủ tục định nghĩa cho các mạch X21 đợc thực hiện qua
một dạng chuyển mạch kênh. X21 sử dụng các chuổi ký tự điều khiển tạo ra
một tập không giới hạn các khả năng tuy chọn dành cho các yêuànafu trong

b) DLP đồng bộ
Phơng thức này không dùng các bit đặc biệt nh phơng thức trên mà nó
chèn các kí tự đặc biệt nh SYN (Synchronization), EOT (end of
transmission) hay đơn giản chỉ là mộ cờ giữa các dữ liệu của ngời sử dụng
để báo hiệu cho ngời nhận biết dữ liệu
Hệ thống truyền thông đòi hỏi hai mức đồng bộ hoá:
-ở mức vật lý: để giữ đồng bộ giữa các đồng hồ của ngời gửi và ngời nhận.
-ở mức liên kết dữ liệu: để phân biệt dữ liệu với các cờ và các bit điều khiển
khác.
2.Giao thức hớng kí tự.
Giao thức hớng kí tự đợc xây dựng dựa vào một ký tự đặc biệt trên một bộ
mã chuẩn nào đó. Giao thức này dùng cho các ứng dụng điểm nối điểm lẫn
nhiều điểm. Giao thức này áp dụng cho 3 phơng thức truyền khác nhau: Một
chiều, hai chiều luân phiên, hai chiều đồng thời.
Phơng thức một chiều có các giao thức truyền tệp Kermit cho phép truyền
file giữa hai máy PC hay giữa một máy PC và một máy chủ.
Phơng thức hai chiều luân phiên có giao thức BSC (Binary Synchronous
Control). Giao thức này đợc ISO lấy làm cơ sở để xây dựng giao thức hớng
kí tự chuẩn quốc tế với tên gọi Basic Mode.
Phơng thức hai chiều đồng thời có rất ít giao thức
Giao thức BSC áp dụng cho trờng hợp điểm - điểm, hoặc nhiều điểm với ph-
ơng thức truyền hai chiều luân phiên.
Các kí tự đặc biệt bao gồm:
SOH (start of header) để chỉ bắt đầu của phần header của một đơn vị thông
tin chuẩn.
STX (start of text) chỉ sự kết thúc một header và bắt đầu của phần dữ liệu.
11
Data lind Protocols(DLPs)
Asynchronous Synchronous
Character-Oriented Bit-Oriented

Trạm A sau khi gửi lệnh nếu quá một thời gian mà không nhận đợc trả lời
của B hay nhận đợc trả lời sai thì nó sẽ chuyển sang trạng thái phục hồi.
+ Mời nhận tin:
trạm A muốn mời trạm B nhạn tin thì lúc đó trạm gửi tới trạm B lệnh nh
sau:
EOT B ENQ
Nếu trạm B nhận tin thì nó sẽ gửi ACK để trả lới nếu không thì nó sẽ gửi
NAK để trả lời.
Nếu trạm B sau mộ tthời gian mà không nhận đợc trả lời hay trả lời sai thì
nó chuyển sang trạng thái phục hồi.
+ Yêu cầu trả lời:
12
Một trạm cần trạm kia trả lời một yêu cầu nào đó đã gửi đi thì nó chỉ cần
gửi lệnh ENQ.
Ngừng truyền tin gửi lệnh EOT
Muốn giải phóng liên kết gửi lệnh DLE và EOT
+ Trạng thái phục hồi nh sau:
Lặp lại lệnh đã gửi n lần hay gửi yêu cầu trả llơi n lần hay kết thcú truyền
bằng cách gửi lệnh EOT
3.Giao thức hớng bit
- Giao thức HDLC (Hight- level Data link control)
HDLC là giao thức hớng bit nghĩa là các phần tử của nó đợc xây dựng từ
cấu trúc nhị phân và khi nhận dữ liệu thì nó sẽ đợc tiếp nhận lần lợt từng
bit một. Giăo thức này sử dụng cho cả hai trờng hợp: điểm -điểm và nhiều
điểm với phơng thức truyền hai chiều đồng thời.
Khung HDLC có hai khuôn dạng: chuẩn và mở rộng.
Khuôn dạng tổng quát của một khung của HDLC nh sau:
Flag Address Control Informtion FSC Flag
Hình: Khuôn dạng tổng quát một khung HDLC
+Flag đánh dấu bắt đầu và kết thcú một khung Frame, vùng này có kích

Phơng thức trả lời dị bội cũgn đợc sử dụng trong trờng hợp cấu hình
không cân bằng nhng các trạm tớ đợc phép tiến hành việc truyền tin mà
không cần sự cho phép của trạm chủ. Phơng thức này dùng trong trờng
hợp điểm -điểm với phơng thức truyền hai chiều.
, SABM (Set Asynchronous Balanced Mode): Phơng thức dị bội cân bằng.
1 1 1 1 P 1 0 0
Phơng thức này sử dụng trong trờng hợp điểm- điểm với phơng thức
truyền hai chiều, hai trạm đều có vai trò nh nhau.
, DISC (Disconnect) đợc sử dụng để giải phóng liên kết khi cần thiết
1 1 0 0 P 0 1 0
, UA (Unnumbered Acknowledgement) dùng để trả lời cho các khung loại
U khác.
1 1 0 0 F 1 1 0
Khung loại I (Information Frames): dùng để chứa thông tin của ngời
sử dụng và trong đó có đánh số thứ tự để kiểm soát. Các bit của vùng
control đối với khung loại I nh sau:
0 N(S) P/F N(R)
N(S) là chỉ số thứ tự của khung I mà trạm gửi đang chờ để nhận và cho
biết rằng đã nhận tốt các khung có số thứ tự từ khung này trở về trớc.
Khung loại S (Supervisory Frames) là khung điều khiển dùng để kiểm
soát lỗi và kiểm soát luồng dữ liệu trong quá trình truyền tin. Các bit
của vùng control đối với khung loại S nh sau:
1 0 S S P/F N(R)
Hai bit S để định danh nh vậy có 4 khung loại S:
, Nếu hai bit S có giá trị 0 0 thì ta có khung RR (Receive Ready), khung
này dùng để thông báo rằng trạm này sẵn sàng nhận tin và cũng thông
báo rằng đã nhận tốt các khung cho đến khung thứ N(R)-1.
, Nếu hai bit có giá trị 1 0 thì ta có khung RNR (Receive Not Ready),
khung này dùng để thông báo rằng trạm này không sẵn sàng nhận tin
đồng thời đã nhận tố các khung có thứ tự đến N(R)-1.

2. Kỹ thuật chọn đờng.
Chọn đờng là việc lựa chọn một con đờng để truyền một đơn vị dữ liệu từ
trạm nguồn đến trạm đích. Chính vì vậy kỹ thuật chọn đờng phỉa thực hiện
hai yếu tố sau đây:
- Quyết định chọn đờng theo tiêu chuẩn tối u nào đó.
- Cập nhật thông tin chọn đờng theo chức năng đã nói ở trên
Có nhiều kỹ thuật chọn đờng khác nhau:
- Nếu dựa vào sự phân tán của các chức năng chọn đờng trên các nút
của mạng thì ta có hai kỹ thuật chọn đờng là tập trung và phân tán.
- Nếu dựa vào sự thích nghi với trạng thái hiện hành của mạng thì ta có
kỹ thuật chọn đờng tĩnh hay thích nghi.
Ngoài ra, kỹ thuật chọn đờng còn phụ thuộc vào một số tiêu chuẩn tối u
nào đó nh topo mạng, thông lợng, mục đích sử dụng v.v Tiêu chuẩn tối u
này phụ thuộc vào ngời thiết kế hay quản lý mạng.
Kỹ thuật chọn đờng tập trung:
Kỹ thuật này đợc đặc trng bởi sự tồn tại của một vài trung tâm điều
khiển mạng thực hiện việc chọn đờng, sau đó gửu các bảng chọn đờng
(routing table) tới tất cả các nút dọc theo con đờng đã đợc chọn đó. Tất cả
thông tin cần dùng cho viẹc chọn đờng đợc cất giữ tại trung tâm điều
khiển mạng. Các nút mạng có thể không gửi bất kỹ thông tin vào về trạng
thái của chúng tới trung tâm, có thể gửi theo định kỳ, hoặc có thể gửi khi
xảy ra một sự kiện nào đó. Trung tâm điều khiển sẽ cập nhật các bảng
chọn đờng dựa vào các thông tin nhận đợc đó.
Kỹ thuật chọn đờng phân tán.
Kỹ thuật này không tồn tại các trung tâm điều khiển, các quyết định đợc
thực hiện tại mỗi nút của mạng. Tuỳ theo độ thích nghi của giải thuật mà
có sự trao đổi thông tin giữa các nút mạng.
Kỹ thuật chọn đờng không thích nghi
Còn gọi là kỹ thuật chọn đờng tĩnh có thể là tập trung hay phân tán nhng
nó không đáp ứng với mọi sự thay đổi trên mạng. Việc chọn đờng này đ-

pháp cho các vấn đề trên.
Giải thuật tìm đờng tối u:
Giải thuật chọn đờng tập trung (Dijkstra)
Vấn đề đặt ra là tìm con đờng có độ dài ngắn nhất từ một nút cho trớc
tới mỗi nút còn lại của mạng. Giải thuật này sẽ từng bớc thiết kế một con đ-
ờng ngắn nhất có gốc tại nút nguồn cho tới khi nút xa nhất của mạng đã đợc
đa vào.
Giả sử có một mạng có liên kết hia chiều đồng thời và độ dài (hay còn gọilà
giá) cho cả hai chiều đợc ghi bên mỗi liên kết. Gọi l(i,j) là độ dài đờng nối
trực tiếp hai nút i và j.
L(i, j) = nếu tồn tại đờng nối giữa hai nút.
N
k
là tập hợp tạo thành bởi k+1 phần tử: nguồn và k nút gần nguồn nhất sau k
bớc thực hiện giải thuật.
D
k
(n) là độ dài từ nguồn tới nút n theo con đờng ngắn nhất bao hàm trong N
k
.
Với sơ đồ mạng sau, giả sử nút 1 là nút nguồn:
1
2 2
2 2 3
1 1
1
16
2
2
2

(w), l(w,v)] vN
k
Thuật toán này sẽ dừng lại khi tập N chứa tất cả các nút.
Với mạng ở trên thì có 6 nút mạng, áp dụng giải thuật trên thì sau 6 bớc ta xẽ
có một con đờng tối u từ 1 đến các nút khác với bảng chọn đờng nh sau:
Nguồn Đích Nút kế tiếp
1 2 2
1 3 3
1 4 3
1 5 2
1 6 3
1
2
1 1 1
<Giải thuật chọn đờng phân tán (Ford và Fulkerson)
Giải thuật này cho phép tìm con đờng ngắn nhất từ tất cả các nút tới một đích
chung. Giải thuật này thực hiện các bớc lặp sau k bớc thì mỗi nút đợc đánh
dấu bởi cặp giá trị (n
k
(v), D
k
(v)), trong đó:
D
k
(v) là độ dài cực tiểu hiện tại từ một nút v bất kỳ tới đích;
n
k
(v) là nút tiếp theo hiện tại trên con đờng tối u từ nút v tới đích đợc
tính ở bớc k.
Giả sử để tính con đờng ngắn nhất từ tất cả các nút tới nút 1, ta thực hiện nh

(w
1
)+l(v,w
1
)=min [D
k-1
(w)+l(v,w)] w, N
v
Quá trình này sẽ dừng lại khi cặp giá trị đánh dấu của mỗi nút giữ nguyên
không thay đổi nữa. Việc tính toán và cập nhật ở mỗi bớc đợc thực hiện theo
17
1
2 5
6
43
thứ tự số nhng không ảnh hởng đến sự hội tụ của giải thuật. áp dụng giải
thuật này đối với sơ đồ mạng trên thì ta cũng có cây chọn đờng nh thuật toán
chọn đờng tập trung.
3. Giao thứ X25 PLP (Packet Level Protocol)
CCITT công bố khuyến nghị về họ giao thức X25 sử dụng cho cả 3 tầng
1,2,3 trong các mạng chuyển mạch gói công cộng PPSN (public packet
swiched networks), trong đó:
Giao thức X25.1 tơng ứng với giao thức X21
Giao thức X25.2 tơng ứng với giao thức LAP-B
Mãi đến năm 1984, CCITT và ISO phối hợp nhau và ban hành chuẩn X25
PLP cho tầng 3 đằc tả các giao diện DTE/DCE và DTE/DTE với DCE đóng
vau trò là nút mạng chuyển mạch gói X25
Giao thức X25 PLP định nghĩe 2 loại liên kết logic:
-VC(VIRTUAL CIRCUIT) là liên kết ảo có tính tạm thời đợc thiết lập và
giải phống bởi các thủ tục của X25 PLP

thức liên kết VC và PVC.
+Restart confirmation: Xác định khởi động lại giao diện, sử dụng hai
phơng thức liên kết VC và PVC.
Thủ tục Restart nhằm khởi tạo lại toàn bộ tầng 3 của giao diện DTE/DCE
mà cụ thể là nó xoá bỏ toàn bộ các liên viễn.
18
X25 có hơn 40 thủ tục phụ:
Các thủ tục này một số có thể đợc cung cấp bởi mạng, còn một số khác
lại đợcdùng bởi một ngời sử dụng cụ thể theo yêu cầu. Một số thủ tục đợc
chọn để dùng trong một giai đoạn thoả thuận trớc, một số khác đợc yêu
cầu trên từng liên kết và đợc khai báo trong gói tin Call request, lúc này
chúgn chỉ có hiệu lực đối với liên kết đó.
Sau đây là một số thủ tục phụ của X25 PLP:
- Flow Control Parameter Negociation: Có chức năng cho phép thơng l-
ợng về kích thớc cửa sổ và độ dài tối đa của vùng user data cho mỗi h-
ớng của liên kết
- Throughput Class Negociation: Cho phép thơng lợng về thông lợng
của dữ liệu truyền qua một số liên kết trong phạm vi từ 75bps đến
48Kbps.
- Non standard Default Packet Sizes: Cho phép thay đổi giá trị ngầm
định của khích thứơc vùng User data trong các gói tin Data.
- Non standard Default Window Sizes: Cho phép thay đổi giá trị ngầm
định của cửa sổ.
- End to End transit Delay Negociation: Cho phép thay đổi về độ trễ
truyền dẫn từ nguồn tới đích.
- Fast select: Cho phép điều khiển các ứng dụng hớng giao tác, trong đó
ít nhất một hành động hỏi/đáp xảy ra.
Khuôn dạng các gói tin trong giao thức X25PLP:
Q D 0 1
Logic

X25 PLP thì phải cắt nhỏ thành nhiều gói tin.
Để bên nhận có thể tập hợp đủ các gói tin đã bị cắt ta dùng bit M để đánh
dấu gói tin cuối cùng trong dãy các gói tin đó.
Nếu M=0 thì vẫn còn gói tin tiếp theo sau
Nếu M=1 thì đó là gói tin cuối cùng.
P(S): số hiệu của gói tin đang chờ để nhận. ở dạng chuẩn thì P(S) chiếm 3
bit, ở dạng mở rộng P(S) chiếm 7 bit.
Packet Type Identifier (PTI): Mã phân biệt các kiểu gói tin. Tất cả các gói
tin của X25 PLP đều cùng chứa tham số PTI chỉ trừ gói tin dữ liệu thờng là
không có. Mã của vùng này nh sau:
0 0 1 0 0 0 1 1
User Data: Dữ liệu khẩn của ngời sử dụng. Đối vớ gói tin dữ liệu khẩn thì
vùng này không vợt quá 32 byte, còn đối với gói tin dữ liệu thờng thì vùng
này có độ dài tối đa ngầm định là 12 8 byte.
Khuôn dạng của gói tin điều khiển
0 0 0/1 1/0 Logical
Channel Identifier
Packet type identifier
Ađitional Information
Hình 4: Khuôn dạng của gói tin điều khiển
Đối với gói tin điều khiển thì chức năng của các tham số tơng tự nh trên.
Ađitional Information là vùng thông tin bổ sung trong các gói tin điều khiển
đợc xác định tuỳ theo kiểu gói tin cụ thể.
Kiểm soát luồng dữ liệu trong X25 PLP
Để kiểm soát luồng dữ liệu tại mỗi nút, giao thức này sử dụng cơ chế cửa sổ.
Cửa sổ là gì?
ở mỗi hớng truyền dữ liệu trên mỗi liên kết, một cửa sổ đợc xác định nh là
một tập hợp có thứ tự của n số hiệu P(S) liên tiếp của các gói tin data đợc
phép truyền qua giao diện DTE/DCE. Nh vậy cửa sổ đợc xác định bởi một
giới hạn trên và một giới hạn dới. Giới hạn trên là giá trị P(S) của gói tin đầu

tin ở xa.
Mối quan hệ giữa X.25, X.3, X.28, X.29 đợc diễn tả nh sau: X.25 X.25 X.25

X.28 X.29
Hình 10: Mối quan hệ giữa X.25, X.3, X.28, X29.
Dịch vụ OSI cho tầng mạng
Bên cạnh các giao thức ISO còn định nghĩa các dịch vụ mà tầng mạng
dùng để cung cấp cho các thực thể ở tầng trên dới dạng các hàm dịch vụ
nguyên thuỷ.
Trong trờng hợp có liên kết
Việc truyền thông đựơc thực hiện qua 3 giai đoạn: thiết lập liên kết, truyền
dữ liệu, giải phóng liên kết
Việc thiết lập liên kết đợc cung cấp bởi 4 hàm nguyên thuỷ sau:
- N_CONNECT. Request (Called Address, Calling Address, Receipt
Confirmation Selection, Expeđited Data selection, QOS Parameter
set, NS User Data).
21
C-DTE
PAD(X.3) DCE DCE P-DTE
- N_CONNECT. Indication (Called Address, Calling Address, Receipt
Confirmation Selection, Expedited Data selection, QOS Parameter
set, NS- User Data).
- N_CONNECT. Response (Responding Address, Receipt Confirmation
Selection, Expedited Data selection, QOS- Parameter set, NS- User
Data).
- N_CONNECT. Confirm ( Responding Address, Receipt Confirmation
Selection, Expedited Data selection, QOS-Parameter set, NS- User

service , US- User Data).
-N-UNITDATA.Indication (Source Address, Destination Address, Quality
of service, US- User Data).
Trong đó địa chỉ nguồn và địa chỉ đích là các địa chỉ liên mạng toàn cục
định dang một cách duy nhất các hệ thống cuối. Quality of service bao
gồm các tham số sau:
- Transit Delay: Chỉ thời gian cần thiết giữa một N-UNITDATA.request
và N-UNITDATA.Indication tơng ứng.
22
- Protection: Bảo vệ tránh các truy cập bất hợp pháp
- Cost Determinants: Cho phép ngời dùng chỉ rõ tính chất của giá cớc
phơng tiện đợc sử dụng.
- Residual Error Probability: Chỉ ra xác suất một NSDU có thể bị mất,
bị trùng lặp hay bị lỗi khi nhận.
- Priority: Độ u tiên đối với mỗi NSDU (network service data unit), đặc
biệt khi cần loại bỏ chúng để phục hồi các tài nguyên.
Giao thức, ISO công bố chuẩn IP (Internet Protocol) để cung cấp các
dịch vụ mạgn không liên kết và cung cấp khả năng nối kết mạng. IP sử
dụng hai laọi đơn vị dữ liệu là Data PDU và error report PDU.
Công nghệ chuyển mạch nhanh.
Khi nhu cầu truyền thông ngày càng cao thì công nghiệp truyền dẫn đòi
hỏi chất lợng cũng nh tốc độ ngày càng cao. Các mạng chuyển mạch gói
với giao thức X25 thông lợng tối đa 64 kbps cha đáp ứng đựơc nhu cầu
truyền thông. Trong khi hiệu năng của công nghệ X25 cha đựơc cải thiện
thì quá trình đầu t cho việc tăng tốc độ chuyển mạch tại các nút mạng
đang có tên chung là FPS (Fast packet Switching) và đợc xây dựng dựa
trên hai kỹ thuật cơ bản là Frame Relay và Cell relay.
-Frame relay dùng các đơn vị dữ liệu có kích thớc thay đổi, kỹ thuật này
cho phép vợt ngỡng 64 Kbps của X25 nhng thông lợng tối đa chỉ 2Mbps.
Kỹ thuật này có thể càiđặt cho các liên kết PVC là liên kết logic luôn sẵn

định danh các dữ liệu đợc thiết lập. Khi một liên kết dữ liệu đợc thiết lập thì
nó đợc gán một DLCI và giá trị này luôn đợc khai báo trong tất cả các khun
dữ liệu và Frame điều khiển liên quan tới liên kết đó. DLCI có ý nghĩa cục
bộ và đợc dùng để chọn đờng. ở mỗi nút, khi nhận đợc một trong khugn dữ
liệu thì chơng trình điều khiển đang cài trong đó sẽ đọc giá trị DLCI trong
vùng header và kết hợp với số liệu của đờng truyền vào để xác định giá trị
DLCI tơng ứng và đờng truyền ra. Giá trị DLCI mới này sẽ đa vào hàng đợi
để gửi tiếp đờng đã chọn.
Các Frame liên quan đến một liên kết dữ liệu nào đó có thể đợc tạo ra ở các
thời điểm ngẫu nhiên mà nhiều liên kết dữ liệu có thể đồng thời phân chia
cho một đờng truyền vật lý nên hiện tợng nghẽn mạch có thể xảy ra với một
đờng truyền nào đó khi lu thông trong mạch quá lớn.
Bit CF ( Congestion Forward), CB (Bongestion Bacdward) và DE (Descard
Eligibility) trong vùng Header dùng để kiểm soát hiện tợng tắt nghẽn . Khi
chơng trình điều khiển chuyển tiếp một khung vào hàng đợi ra thì nó sẽ kiểm
tra kích thứơc của hàng đợi, nếu vợt quá nột giới hạn cho trớc thì nó sẽ thông
báo tình trạng này cho ngời sử dụng ở hai đầu liên kết bằng cách đặt giá trị
cho bit CF hoặc CB tuỳ theo chiều đi hay về của khung.
Nếu chơng trình điều khiển nhận đợc thông báo về tình trạng nghẽn mạch thì
nó sẽ giảm tốc độ gửi Frame của nó hay loại bỏ bớt khung cho tới khi không
còn tín hiệu tắt nghẽn nữa.
Kỹ thuật ATM
Kỹ thuật truyền bất đồng bộ là ứng dụng cấp cao của mạng chuyển mạch
gói, cung cấp một mạng dồn kênh và chuyển mạch tốc độ cao để truyền các
gói dữ liệu có kích thớc cố định qua mạng.
Trong mạng sử dụng kỹ thuật ATM thì có một Public NNI (Public network
interface) xác định giao diện giữa một mạng ATM công cộng với một ATM
Switch và một Private UNI ( Private User Network Interface) là giao diện
giữa ngời sử dụng cuối với một ATM Switch dùng riêng.
Trong mạng ATM thì cũng đợc phân tầng nhng không tơng ứng hoàn toàn

theo các ô 53 byte thay vì truyền theo khung có chiều dài thay đổi. Các ô này
có chứa 48 byte thông tin ứng dụng và 5 byte chứa dữ liệu điều khiển là đoạn
đầu của ATM.
Trong kỹ thuật này các tế bào chứa các kiểu dữ liệu khác nhau đợc đổ vào
mộtđờng dãn chung gọi là đờng dẫn ảo. Trong một đờng dẫn ảo cso thể có
nhiều kênh ảo, mỗi kênh đợc sử dụng bởi một ứng dụng cụ thể nào đó tại
thời điểm hiện tại.
Tế bào ATM có khuôn dạng nh sau:
GFC
(Generic Flow Control)
VPI
(Virtual Path Identifier)
VPI
(Virtual Path Identifier)
VCI
(Virtual Channel Identifier)
VCI
VCI PT (payload Type) C(Cell loss
Priority)
HEC (Header Error Control)
Khuôn dạng trên chỉ đúng với trờng hợp UNI, còn trong trờng hợp NNI thì 4
bit GFC đợc dùng cho cả tham số VPI.
Tham số GFC dùng để kiểm soát luồng dữ liệu
Tham số VPI đợc dùng để định danh đờng dẫn ảo.
Tham số VCI dùng để xác định chính xác kênh ảo cần chuyển tế bào ATM
đi.
Trong trờng hợp UNI, cặp tham số VPI/VCI có 24 bits sẽ cho phép địa chỉ
hoá 16 triệu kênh ảo.
Tham số PT dùng để chỉ rõ kiểu dữ liệu chứa trong tế bào ATM.
Tham số C dùng để chỉ độ u tiên khi sử dụng loại bỏ các tế bào ATM, C=1 là