Tài liệu Mạng chuyển mạch gói (Packet switching): Chương 6:
Mạng chuyển mạch gói
(Packet switching)
bvhieu@cse.hcmut.edu.vn
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Nội dung
Giới thiệu mạng chuyển mạch gói
Tìm đường
X.25
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Nội dung
Giới thiệu mạng chuyển mạch gói
Tìm đường
X.25
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Hạn chế của chuyển mạch mạch
Các tài nguyên được dành riêng cho cuộc
gọi
Hầu hết thời gian kết nối đường truyền rảnh
Tốc độ dữ liệu cố định
Thiết bị ở hai đầu phải chạy cùng tốc độ
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Nguyên lý chuyển mạch gói
Dữ liệu được truyền thành các gói nhỏ
Thông thường là 1000 byte
Dữ liệu lớn được chia thành chuỗi các gói nhỏ để
truyền
Mỗi gói gồm dữ liệu cộng thêm thông tin điều
khiển
Các gói được nhận, lưu tạm thời và truyền
cho node kế tiếp (store and forward)
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Ưu điểm chuyển mạch gói
Tăng hiệu suất đường truyền
Một kết nối node-node có thể dùng chung bởi
...
76 trang |
Chia sẻ: hunglv | Lượt xem: 1961 | Lượt tải: 2
Bạn đang xem trước 20 trang mẫu tài liệu Mạng chuyển mạch gói (Packet switching), để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
Chương 6:
Mạng chuyển mạch gói
(Packet switching)
bvhieu@cse.hcmut.edu.vn
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Nội dung
Giới thiệu mạng chuyển mạch gói
Tìm đường
X.25
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Nội dung
Giới thiệu mạng chuyển mạch gói
Tìm đường
X.25
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Hạn chế của chuyển mạch mạch
Các tài nguyên được dành riêng cho cuộc
gọi
Hầu hết thời gian kết nối đường truyền rảnh
Tốc độ dữ liệu cố định
Thiết bị ở hai đầu phải chạy cùng tốc độ
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Nguyên lý chuyển mạch gói
Dữ liệu được truyền thành các gói nhỏ
Thông thường là 1000 byte
Dữ liệu lớn được chia thành chuỗi các gói nhỏ để
truyền
Mỗi gói gồm dữ liệu cộng thêm thông tin điều
khiển
Các gói được nhận, lưu tạm thời và truyền
cho node kế tiếp (store and forward)
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Ưu điểm chuyển mạch gói
Tăng hiệu suất đường truyền
Một kết nối node-node có thể dùng chung bởi
nhiều gói
Các gói xếp hàng và truyền đi nhanh nhất có thể
Chuyển đổi tốc độ dữ liệu
Mỗi trạm kết nối với node cục bộ bằng tốc độ của
trạm
Các node đệm dữ liệu nếu cần thiết để cân bằng
tốc độ
Các gói được nhận ngay khi mạng đang bận
Việc phát có thể chậm lại
Có thể phân độ ưu tiên cho các thông báo
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Kỹ thuật chuyển mạch
Trạm chia thông báo dài thành nhiều gói nhỏ
Từng gói được gởi lần lượt vào mạng
Các gói được xử lý theo 2 cách
Datagram
Virtual circuit
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Datagram
Mỗi gói được xử lý độc lập
Các gói có thể đi theo bất cứ đường thích
hợp nào
Các gói có thể đến đích không theo thứ tự
gởi
Các gói có thể thất lạc trên đường đi
Bên nhận phải sắp xếp lại các gói mất trật tự
và khôi phục các gói thất lạc
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Minh họa Datagram
2
1
3 2 1
3
(c)
3
1
2
(b)
(a)
(d)
(e)
2 1
3
3
2
1
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Virtual circuit
Đường đi được tạo trước khi gởi các gói dữ
liệu
Các gói yêu cầu cuộc gọi và chấp nhận cuộc
gọi được dùng để tạo kết nối (handshake)
Mỗi đường đi được gán một số ID
Mỗi gói chứa ID của đường đi thay vì địa chỉ
máy đích
Không cần tìm đường cho từng gói
Đường đi không dành riêng
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Minh họa Virtual circuit
2
1
3
2
3 2 1
3
(c)
1
3
(b)
(a)
(d)
(e)
2 1
3
2
1
Bộ môn Kỹ thuật máy tính
Khoa Khoa
So sánh Virtual Circuit Datagram
Sự trình tự và điều khiển lỗi ?
Thời gian trễ đễ truyền được một gói ?
Thời gian trễ đễ truyền các gói sau gói đầu
tiên ?
Khả năng chịu lỗi ?
Tính linh động về đường đi ?
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Vấn đề kích thước gói
1
Data
1
Data
Header
(a) 1-packet message (b) 2-packet message (c) 5-packet message (d) 10-packet message
Data
Data
Data
2
Data
1
Data
2
Data
1
Data
2
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
2
3
4
5
1
2
3
4
5
1
2
3
4
5
Figure 10.14 Effect of Packet Size on Transmission Time
X a b Y
X a b Y
X a b Y
X a b Y
T
im
e
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Circuit vs. Packet Switching
Người gởi được thông
báo nếu các gói không
được phân phát
Người gởi có thể được
thông báo nếu các gói
không được phân phát
Tín hiệu bận nếu bên
nhận không sẵn sàng
Trễ do quá trình thiết lập,
trễ truyền các gói
Trễ truyền các góiTrễ do quá trình thiết lập,
nhưng thời gian trễ trong
quá trình truyền không
đáng kể
Đường đi được thiết lập
cho toàn bộ quá trình
trao đổi
Đường đi được thiết lập
cho mỗi gói
Đường truyền dẫn được
thiết lập cho toàn bộ quá
trình trao đổi
Thông báo được lưu trữ
cho đến khi đến phân
phát
Thông báo có thể được
lưu trữ cho đến khi đến
phân phát
Thông báo không được
lưu trữ
Đủ nhanh cho ứng dụng
tương tác
Đủ nhanh cho ứng dụng
tương tác
Đủ nhanh cho ứng dụng
tương tác
Dữ liệu truyền theo góiDữ liệu truyền theo góiDữ liệu truyền liên tục
Đường truyền dẫn không
dành riêng
Đường truyền dẫn không
dành riêng
Đường truyền dẫn dành
riêng
Virtual Circuit PacketsDatagram PacketsCircuit Switching
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Circuit vs. Packet Switching (tt)
Tốn kém dữ liệu cho mỗi
gói
Tốn kém dữ liệu cho mỗi
gói
Không tốn chi phí dữ liệu
sau khi thiết lập
Linh động sử dụng băng
thông
Linh động sử dụng băng
thông
Truyền dẫn băng thông
cố định
Chuyển đổi tốc độ và
bảng mã
Chuyển đổi tốc độ và
bảng mã
Thường không cần
chuyển đổi tốc độ và
bảng mã
Mạng có thể sẽ chịu
trách nhiệm cho chuỗi
các gói
Mạng có thể sẽ chịu
trách nhiệm cho các gói
đơn lẻ
User chịu trách nhiệm
khi các thông báo bị thất
lạc
Node chuyển mạch nhỏNode chuyển mạch nhỏChuyển mạch cơ điện
hoặc được điều khiển
bởi máy tính
Quá tải có thể khóa việc
thiết lập; tăng thời gian
trễ của gói
Quá tải sẽ tăng thời gian
trễ của gói
Quá tải sẽ khóa việc
thiết lập; không trễ khi
đường truyền đã được
thiết lập
Virtual Circuit PacketsDatagram PacketsCircuit Switching
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Hoạt động bên ngoài – bên trong
Giao tiếp giữa các node mạng (bên trong)
Datagrams hoặc virtual circuits
Giao tiếp giữa trạm và node mạng (bên
ngoài)
Kết nối (Connection oriented)
Trạm yêu cầu kết nối luận lý (virtual circuit)
Tất cả các gói được đánh dấu thuộc về kết nối đó và
được đánh số thứ tự
Mạng phân phát các gói theo thứ tự
Dịch vụ mạch ảo bên ngoài
Không kết nối (Connectionless)
Các gói được xử lý độc lập
Dịch vụ datagram bên ngoài
Bộ môn Kỹ thuật máy tính
Khoa Khoa
External Virtual Circuit and External Datagram
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Internal Virtual Circuit and Internal Datagram
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Tổ hợp các công nghệ
External virtual circuit, internal virtual circuit
Đường dành riêng thông qua mạng
External virtual circuit, internal datagram
Mạng xử lý mỗi gói riêng biệt
Mạng lưu trữ các gói tại node đích để sắp xếp lại
thứ tự
External datagram, internal datagram
Các gói được đối xử một cách độc lập bởi cả
mạng và trạm
External datagram, internal virtual circuit
Không được sử dụng
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Nội dung
Giới thiệu mạng chuyển mạch gói
Tìm đường
X.25
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Tìm đường trong Circuit switching
Mạng chuyển mạch công cộng có cấu trúc
cây
Đường đi tĩnh (không thay đổi theo thời gian)
Có thể cải tiến bằng Alternate routing
Thêm các đường kết nối giữa các trung tâm
chuyển mạch
Liệt kê các đường đi có thể
Đường đi được chọn theo độ ưu tiên (tốc độ, chi
phí, thời điểm...)
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Tìm đường trong Packet switching
Phức tạp, rất quan trọng
Các đặc tính yêu cầu
Chính xác (correctness)
Đơn giản (simplicity)
Mạnh mẽ (robustness)
Ổn định (stability)
Công bằng (fairness)
Tối ưu (optimality)
Hiệu quả (efficiency)
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Tiêu chuẩn đo tính hiểu quả
Được dùng đánh giá đường đi tốt
Số chặng đường (hop) là tối thiểu
Đơn giản
Không chính xác
Chi phí (cost) tối thiểu
Các yếu tố băng thông, tải hiện tại... được lượng
hóa thành chi phí
Phức tạp hơn
Chính xác hơn
Được dùng chủ yếu hiện nay
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Yếu tố quyết định chiến thuật tìm đường
Thời điểm quyết định
Mạch ảo hay theo từng gói (packet)
Nơi quyết định
Phân tán (Distributed)
Được thực hiện tại từng node
Tập trung (Centralized)
Được thực hiện tại một node chuyên biệt
Tại nguồn gởi (Source)
Được thực hiện tại node gửi
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Yếu tố quyết định chiến thuật tìm đường
Nguồn thông tin về mạng
Quyết định tìm đường thông thường (không phải
luôn luôn) được dựa trên các thông tin về mạng
Tìm đường phân tán (Distributed routing)
Node sử dụng các thông tin cục bộ
Có thể thu thập thông tin từ các node kế cận
Có thể thu thập thông tin từ các node trên đường tiềm
năng
Tìm đường tập trung (Central routing)
Thu thập thông tin từ tất cả các node
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Yếu tố quyết định chiến thuật tìm đường
Thời điểm cập nhật thông tin
Khi nào thông tin sẽ được cập nhật
Tìm đường cố định: không được cập nhật
Tìm đường động (adaptive): cập nhật sau một
khoảng thời gian ấn định trước
Thời gian này nên lớn hay nên nhỏ ?
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Các chiến thuật tìm đường
Fixed routing
Flooding routing
Random routing
Adaptive routing
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Fixed Routing
Đường đi cố định, không thay đổi
Đường đi được xác định dùng giải thuật chi
phí tối thiểu
Đường đi có thể thay đổi nếu có sự thay đổi
cấu hình mạng
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Fixed routing - Hiện thực
Figure 12.2 Example Packet-Switching Network
8
5
2
2
23 3
3
3
1
1
1
1
1
7
6
5
8
2
4
1
4 5
6
32
CENTRAL ROUTING DIRECTORY
From Node
1 2 3 4 5 6
1 — 1 5 2 4 5
2 2 — 5 2 4 5
3 4 3 — 5 3 5
4 4 4 5 — 4 5
5 4 4 5 5 — 5
To Node
6 4 4 5 5 6 —
Node 1 Directory
Destination Next Node
2 2
3 4
4 4
5 4
6 4
Node 4 Directory
Destination Next Node
1 2
2 2
3 5
5 5
6 5
Node 2 Directory
Destination Next Node
1 1
3 3
4 4
5 4
6 4
Node 5 Directory
Destination Next Node
1 4
2 4
3 3
4 4
6 6
Node 3 Directory
Destination Next Node
1 5
2 5
4 5
5 5
6 5
Node 6 Directory
Destination Next Node
1 5
2 5
3 5
4 5
5 5
Figure 12.3 Fixed Routing (using Figure 12.2)
CENTRAL ROUTING DIRECTORY
From Node
1 2 3 4 5 6
1 — 1 5 2 4 5
2 2 — 5 2 4 5
3 4 3 — 5 3 5
4 4 4 5 — 4 5
5 4 4 5 5 — 5
To Node
6 4 4 5 5 6 —
Node 1 Directory
Destination Next Node
2 2
3 4
4 4
5 4
6 4
Node 4 Directory
Destination Next Node
1 2
2 2
3 5
5 5
6 5
Node 2 Directory
Destination Next Node
1 1
3 3
4 4
5 4
6 4
Node 5 Directory
Destination Next Node
1 4
2 4
3 3
4 4
6 6
Node 3 Directory
Destination Next Node
1 5
2 5
4 5
5 5
6 5
Node 6 Directory
Destination Next Node
1 5
2 5
3 5
4 5
5 5
Figure 12.3 Fixed Routing (using Figure 12.2)
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Flooding Routing
Không cần thông tin mạng
Node gởi các gói tới mọi node kề
Các gói nhận được sẽ được truyền trên tất
cả các kết nối ngoại trừ kết nối gói đến
Cuối cùng sẽ có một số copy của gói sẽ đến
đích
Gói đến đầu tiên là đi trên đường tốt nhất
(a) First hop
Figure 12.4 Flooding Example (hop count = 3)
1
2
4
3
5
6
(b) Second hop
1
2
4
3
5
6
(c) Third hop
1
2
4
3
5
6
(a) First hop
Figure 12.4 Flooding Example (hop count = 3)
1
2
4
3
5
6
(b) Second hop
1
2
4
3
5
6
(c) Third hop
1
2
4
3
5
6
(a) First hop
Figure 12.4 Flooding Example (hop count = 3)
1
2
4
3
5
6
(b) Second hop
1
2
4
3
5
6
(c) Third hop
1
2
4
3
5
6
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Làm sao dừng việc phát tán
Mỗi gói được đánh số duy nhất
Node có thể ghi nhớ các gói đã đi qua
Loại bỏ các node đã đi qua
Gói chứa số chặng đường tối đa
Mỗi khi truyền, số chặng đường giảm đi một
Dừng phát tán khi số chặng đường bằng 0
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Tất cả các lộ trình đều được thử
Rất mạnh mẽ (robust)
Ít nhất sẽ có một gói đi theo lộ trình với số
chặng ít nhất
Có thể được dùng để thiết lập đường mạch ảo
Tất cả các node đều nhận được packet
Thích hợp trong phát tán thông tin
Đánh giá
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Tư tưởng: dựa trên Flooding routing
Node sẽ chọn một đường liên kết ra để truyền đi
các gói nhận được thay vì gửi ra tất cả các liên
kết
Việc chọn lựa có thể là ngẫu nhiên hoặc xoay
vòng (round robin)
Có thể chọn đường liên kết ra dựa trên việc tính
toán xác suất
Đặc điểm: lộ trình tìm được thông thường
không phải là đường có chi phí tối thiểu hoặc
số chặng nhỏ nhất
Random Routing
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Tư tưởng: dựa trên Flooding routing
Node sẽ chọn một đường liên kết ra để truyền đi
các gói nhận được thay vì gửi ra tất cả các liên
kết
Việc chọn lựa có thể là ngẫu nhiên hoặc xoay
vòng (round robin)
Có thể chọn đường liên kết ra dựa trên việc tính
toán xác suất
Đặc điểm: lộ trình tìm được thông thường
không phải là đường có chi phí tối thiểu hoặc
số chặng nhỏ nhất
Random Routing
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Adaptive Routing
Được sử dụng bởi hầu hết các mạng chuyển
mạch gói
Quyết định tìm đường thay đổi khi các điều
kiện trên mạng thay đổi
Đường kết nối hoặc node trung gian hư
Tình trạng ngẽn mạch thay đổi
Cần biết các thông tin về mạng
Quyết định tìm đường phức tạp
Tradeoff giữa chất lượng của thông tin mạng
và chi phí để truyền thông tin này
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Nhận xét
Ưu điểm
Hiệu suất được cải thiện
Trợ giúp điều khiển nghẽn mạng
Hạn chế
Quyết định tìm đường phức tạp
Tăng tải
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Adaptive Routing – Phân loại
Dựa trên nguồn thông tin về mạng
Cục bộ (isolated)
Các node kề (distributed)
Tất cả các node (centralized)
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Isolated Adaptive Routing
Mỗi node trong mạng tự cập nhật bảng tìm
đường của mình dựa vào các thông tin về
mạng mà node đó học hỏi được
Không trao đổi thông tin tìm đường với các
node khác
Một trong những phương pháp đơn giản nhất
của tìm đường động
Ít dùng (không dùng thông tin có sẵn)
Phù hợp với các mạng có kích thước nhỏ và
hoạt động tương đối ổn định
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Distributed adaptive Routing
Thông tin về tình trạng hiện hành của mạng
sẽ được định kỳ trao đổi, cập nhật giữa các
node
Sau đó thông tin này sẽ được phân bố về lại
các node trong mạng hay một số node trong
mạng làm nhiệm vụ tìm đường
Các node này cập nhật lại bảng routing
Phương pháp này đáp ứng được với những
thay đổi trạng thái của mạng, nhưng đồng
thời cũng làm tăng lưu lượng thông tin trong
mạng
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Centralized adaptive routing
Thông tin về tình trạng hiện hành của mạng
sẽ được định kỳ trao đổi, cập nhật giữa các
node trong toàn mạng.
Sau đó thông tin này sẽ được tập trung về
một máy chủ trong mạng làm nhiệm vụ
routing
Đáp ứng được với những thay đổi tức thời
trong mạng
Nhược điểm là thông tin routing trong toàn
mạng tập trung về một máy nên khi máy này
không hoạt động thì toàn mạng sẽ không
hoạt động được
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Bài toán tìm đường đi ngắn nhất
Cho một đồ thị có trọng số
Tìm đường đi ngắn nhất từ một node đến
các node khác
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Giải thuật Dijkstra
Input
Đồ thị G(V, E) trong đó V là tập đỉnh, E là tập
cạnh có trọng số không âm
Đỉnh nguồn S: S 㱨 V
Output
Đường đi ngắn nhất từ đỉnh nguồn S đến tất cả
các đỉnh còn lại
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Giải thuật Dijkstra
Ký hiệu
Di : đường đi ngắn nhất từ node nguồn S đến
node i tại bước chạy hiện hành của giải thuật
M: tập các đỉnh đã xét tại bước chạy hiện hành
của giải thuật
dij : trọng số trên cạnh nối từ node i đến node j
dij = 0 nếu i trùng j
dij = Eij nếu i khác j
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Giải thuật Dijkstra
Bước 1: khởi động
M = {S}
Di = dSI
Bước 2: cập nhật đường đi ngắn nhất
Chọn đỉnh N 㱨 V sao cho: DN = min {Di} 㱼i 㱨 V
\M
M = M 㱮 {N}
Dj = min {Dj, DN + dNj } 㱼j 㱨 V\M
Bước 3: lặp lại bước 2 cho đến khi M=V
Kết quả Di sẽ là đường đi ngắn nhất từ node
nguồn S đến node i
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Giải thuật Dijkstra
Tìm đường đi ngắn nhất từ node nguồn 1
đến tất cả các node còn lại
1
2
4
3
5
6
1
1
2
1
3
2
2
3
5
5
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Giải thuật Dijkstra
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Giải thuật Bellman - Ford
Input
Đồ thị G(V, E) trong đó V là tập đỉnh, E là tập
cạnh có trọng số
Đỉnh nguồn S: S 㱨 V
Output
Đồ thị có chu trình âm → không tồn tại đường đi
ngắn nhất
Đường đi ngắn nhất từ đỉnh nguồn S đến tất cả
các đỉnh còn lại
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Giải thuật Bellman - Ford
Ký hiệu
D(h)i : đường đi ngắn nhất từ node nguồn S đến
node i có tối đa h đoạn (link).
dij: trọng số trên cạnh nối từ node i đến node j
dij = 0 nếu i trùng j
dij = Eij nếu i khác j
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Giải thuật Bellman – Ford
Bước 1: khởi động
D(1)N = dSN, 㱼N 㱨 V\{S}
Bước 2: cập nhật đường đi ngắn nhất
D(h+1)N = min {D(h)j + djN} 㱼j 㱨 V\{S}
Bước 3: lặp lại bước 2 cho đến khi không có
đường đi mới nào ngắn hơn được tìm thấy
thì dừng
Kết quả D(h)N sẽ là đường đi ngắn nhất từ
node nguồn S đến node N
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Giải thuật Bellman – Ford
Tìm đường đi ngắn nhất từ node nguồn 1
đến tất cả các node còn lại
1
2
4
3
5
6
1
1
2
1
3
2
2
3
5
5
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Giải thuật Bellman – Ford
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Bài tập
Tìm đường ngắn nhất từ node 1 đến các
node còn lại
Theo giải thuật Dijkstra
Theo giải thuật Bellman – Ford
1 2
3 4
5
6
7
1 3
4
2
1
1
2
3
3
5
4
3
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Bài tập
Tìm đường ngắn nhất từ node 1 đến các
node còn lại
Theo giải thuật Dijkstra
Theo giải thuật Bellman – Ford
E
G
H
D
K J
F
C
BA1 1
1
11
1
1
1
2
3
1
4
5
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Đánh giá
Phụ thuộc vào thời gian xử lý của các giải
thuật
Phụ thuộc vào lượng thông tin yêu cầu từ
các node khác
Phụ thuộc vào việc hiện thực
Cùng hội tụ về một lời giải dưới điều kiện
topology tĩnh và chi phí không thay đổi
Nếu chi phí liên kết thay đổi, các giải thuật sẽ
tính lại để theo kịp sự thay đổi
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Tìm đường trong ARPANET (tự đọc)
Thế hệ đầu tiên
1969
Distributed adaptive
Dùng thời gian trễ ước tính làm tiêu chuẩn đánh
giá hiệu quả
Dùng giải thuật tìm đường Bellman-Ford
Các node trao đổi thông tin (các vector thời gian
trễ) với các node kề
Cập nhật bảng tìm đường dựa trên thông tin đến
Không quan tâm đến tốc độ đường truyền, chỉ
quan tâm chiều dài hàng đợi tại các node
Chiều dài hàng đợi không phải là cách đo chính
xác của thời gian trễ
Đáp ứng chậm với nghẽn mạch
Bộ môn Kỹ thuật máy tính
Khoa Khoa
ARPANET – Tìm đường
Thế hệ thứ 2
1979
Dùng thời gian trễ làm tiêu chuẩn đánh giá hiệu
quả
Thời gian trễ được đo trực tiếp
Dùng giải thuật tìm đường Dijkstra
Thích hợp cho mạng có tải trung bình hoặc nhẹ
Khi mạng tải nặng, có ít tương quan giữa thời
gian trễ đo được và thời gian trễ gặp phải
Bộ môn Kỹ thuật máy tính
Khoa Khoa
ARPANET – Tìm đường
Thế hệ thứ 3
1987
Việc tính toán chi phí của liên kết đã được thay
đổi
Thời gian trễ trung bình được đo trong 10 giây
cuối
Bình thường hóa dựa trên giá trị hiện tại và kết
quả trước đó
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Nội dung
Giới thiệu mạng chuyển mạch gói
Tìm đường
X.25
Bộ môn Kỹ thuật máy tính
Khoa Khoa
1976, CCITT
Giao tiếp giữa trạm và mạng chuyển mạch
gói
Phổ biến trong các mạng chuyển mạch gói
và chuyển mạch gói của mạng ISDN
Định nghĩa 3 lớp
Vật lý
Liên kết
Gói
Mạng truyền số liệu X.25
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Lớp vật lý
Giao tiếp giữa trạm và liên kết kết nối trạm
với node mạng
DTE: thiết bị của người dùng
DCE: node mạng
Dùng đặc tả lớp vật lý X.21 (đôi khi thay thế
bằng EIA-232)
Truyền dữ liệu tin cậy thông qua liên kết vật
lý
Cung cấp tuần tự của các frame
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Lớp liên kết
Link Access Protocol Balanced (LAPB)
Tập con của nghi thức HDLC
Xem thêm tài liệu
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Lớp gói (packet)
External virtual circuits
Kết nối luận lý (virtual circuits) giữa các thuê
bao
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Dịch vụ mạch ảo
Cho phép kết nối luận lý
giữa hai trạm
Mạch ảo bên ngoài
Xác định đường đi thông
qua mạng
Mạch ảo bên trong
Thường có mối quan hệ
1-1 giữa mạch ảo bên
ngoài và mạch ảo bên
trong
Có thể sử dụng X25 với
mạng kiểu datagram
Mạch ảo bên ngoài yêu
cầu kênh luận lý riêng
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Các dịch vụ mạch ảo
Virtual Call (SVC – Switched Virtual Circuit)
Virtual circuit được tạo động cho mỗi giao dịch
Permanent virtual circuit
Virtual circuit được gán trước cố định
Không cần thiết lập và xóa kết nối
Fast Select call
Dùng để truyền thông báo/lệnh nhỏ (<128 octet) trong
quá trình thiết lập/xóa kết nối
Bộ môn Kỹ thuật máy tính
Khoa Khoa
X.25 – Định dạng gói
Bộ môn Kỹ thuật máy tính
Khoa Khoa
X.25 – Gói dữ liệu
Số VC (12 bits)
4 bit logical group number
+ 8 bit logical channel number.
Thông thường 2 trường này được xem như một
Dùng để chỉ thị loại kết nối hoặc kênh giữa các
DTE
Các loại kết nối khác nhau cho phép nhiều phiên
giao dịch giữa cùng một cặp DTE
Có thể lên đến 4095 kênh luận lý trên cùng một
đường giao tiếp vật lý
Bộ môn Kỹ thuật máy tính
Khoa Khoa
X25- Gói dữ liệu
Q bit (Qualifier bit)
Không được định nghĩa trong chuẩn
Thường phân biệt các gói chứa dữ liệu (Q=0) và các gói
chứa thông tin điều khiển (Q=1)
D bit
Bằng 0 khi gói này là một phần của gói bị phân mảnh
Cũng được dùng để điều khiển dòng
Khi D=0, điều khiển dòng được thực hiện cục bộ (giữa DTE và cục
bộ DCE)
Khi D=1, điều khiển dòng được thực hiện giữa DTE và DTE ở xa
M bit (More bit)
Gói dữ liệu lớn được phân thành nhiều gói
Ngoại trừ gói cuối cùng, các gói sẽ có bit M bằng 1
P(R) – chỉ số nhận tuần tự
P(S) – chỉ số gởi tuần tự
Bộ môn Kỹ thuật máy tính
Khoa Khoa
X.25 – Gói điều khiển
6 nhóm:
Thiết lập kết nối
Điều khiển dòng
Giám sát
Xác nhận
Chuẩn đoán
Ngắt quãng
Bộ môn Kỹ thuật máy tính
Khoa Khoa
X.25 – Gói điều khiển
Gói thiết lập kết nối
4 loại: Call Request, Incoming Call, Call
Accepted, và Call Connected
Được dùng trong giai đoạn thiết lập mạch ảo
Gói điều khiển dòng
3 loại: Receive Ready (RR), Receive Not Ready
(RNR), và Reject (REJ)
Được dùng trong giai đoạn truyền dữ liệu (các gói
đều chứa P(R))
Bộ môn Kỹ thuật máy tính
Khoa Khoa
X.25 – Gói điều khiển
Gói giám sát
Bao gồm: Restart Request/Indication, Clear
Request/Indication, Reset Request/Indication
Restart Request được dùng trong tình huống xấu
(host crash) để xóa VC do DTE này đang giữ
Clear Request dùng để xóa VC (được chỉ ra trong
VC number)
Reset Request được dùng để reset chỉ số nhận/
gởi tuần tự về 0 trong chế độ truyền dữ liệu
Bộ môn Kỹ thuật máy tính
Khoa Khoa
X.25 – Gói điều khiển
Gói xác nhận
Dùng để xác nhận các yêu cầu trước đó (cho
Restart, Clear, Reset, và Interrupt)
Gói chuẩn đoán
Do mạng tạo ra cho mục đích chuẩn đoán lỗi
Gói ngắt quãng
Được truyền trong quá trình truyền dữ liệu, và
không chứa chỉ số gởi/nhận tuần tự.
Các gói ngắt quãng được truyền tới DTE đích với
độ ưu tiên cao hơn các gói dữ liệu
Bộ môn Kỹ thuật máy tính
Khoa Khoa
X.25 – Set và Reset
Reset
Khởi tạo lại virtual circuit
Số tuần tự được đặt bằng 0
Các gói đang quá cảnh bị mất
Tùy vào các protocol cấp cao để khôi phục lại các gói
bị mất
Kích hoạt bởi việc mất các gói, sai số tuần tự,
nghẽn mạch, mất internal virtual circuit
Restart
Tương đương với yêu cầu xóa tất cả các virtual
circuit
E.g. mất tạm thời việc truy cập mạng
Bộ môn Kỹ thuật máy tính
Khoa Khoa
X.25 – Thủ tục thiết lập kết nối
DTEa 㱻 DCEa 㱻 PSN 㱻 DCEb 㱻 DTEb (DTEa
muốn kết nối với DTEb)
DTEa nhận một virtual circuit number (VCN)
DTEa gởi gói call-request cho DTEb (chứa VCN, địa chỉ
DTEa, địa chỉ DTEb)
DCEa tìm đường đi băng qua mạng PSN cho gói này
đến DCEb
DCEb nhận một VCN mới và gởi gói incoming-call đến
DTEb (gói chứa VCN mới và các thông tin địa chỉ
nguồn/đích)
DTEb chấp nhận kết nối bằng cách gởi gói call-
accepted qua DCEb để đến DCEa
DCEa nhận được gói call-accepted và gởi gói call-
connected tới DTEa
Sau quá trình này, DTEa và DTEb có thể gởi các
gói dữ liệu qua lại
Bộ môn Kỹ thuật máy tính
Khoa Khoa
X.25 – Thủ tục giải phóng kết nối
DTEa 㱻 DCEa 㱻 PSN 㱻 DCEb 㱻 DTEb
(DTEa muốn xóa kết nối với DTEb)
DTEa gởi gói clear-request tới DCEa
DCEa gởi gói clear-indication tới DTEb (thông
qua DCEb)
DTEb gởi clear-indication tới DTEa (thông qua
các DCEb và DCEa)
Bộ môn Kỹ thuật máy tính
Khoa Khoa
Virtual Call
Bộ môn Kỹ thuật máy tính
Khoa Khoa
X.25
Điều khiển dòng và điều khiển sai
HDLC (chương 5)
Chuỗi các gói
Chuỗi đầy đủ các gói
Cho phép khối dữ liệu lớn được truyền qua mạng
với kích thước gói nhỏ hơn mà không mất tính
toàn vẹn của khối
2 loại gói
Các gói A
M bit 1, D bit 0
Chiều dài gói tối đa
Các gói B
Phần còn lại
Các file đính kèm theo tài liệu này:
- Mạng chuyển mạch gói (Packet switching).pdf