-----Circuit Switching

*Quá tải sẽ khóa việc

thiết lập; không trễ khi

đường truyền đã được

thiết lập

*Chuyển mạch cơ điện hoặc được điều khiển

bởi máy tính

**User chịu trách nhiệm

khi các thông báo bị thất

lạc

** Thường không cần

chuyển đổi tốc độ và

bảng mã

** Truyền dẫn băng thông

cố định

** Không tốn chi phí dữ liệu

sau khi thiết lập

*-------Datagram Packets

** Quá tải sẽ tăng thời gian

trễ của gói

** Node chuyển mạch nhỏ

** Mạng có thể sẽ chịu

trách nhiệm cho các gói

đơn lẻ

** Chuyển đổi tốc độ và

bảng mã

** Linh động sử dụng băng

Thông

** Tốn kém dữ liệu cho mỗi

Gói

***----Virtual Circuit Packets

* Quá tải có thể khóa việc

thiết lập; tăng thời gian

trễ của gói

*Node chuyển mạch nhỏ

* Mạng có thể sẽ chịu

trách nhiệm cho chuỗi

các gói

* Chuyển đổi tốc độ và

bảng mã

* Linh động sử dụng băng

Thông

* Tốn kém dữ liệu cho mỗi

gói

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

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

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ướ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

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

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ướ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