Xem mẫu
- om
.c
ng
co
an
Định tuyến trong mạng viễn thông
th
o ng
du
u
cu
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Cơ bản
• Định tuyến là quá trình tìm đường đi giữa hai điểm trong
mạng theo một số yêu cầu cho trước
om
– Đường đi ngắn nhất ?
– Đường có băng thông rộng nhất ?
.c
• Đường đi phải thường phải tối ưu theo một tiêu chí nào đó
ng
• Các gói tin được gửi đi theo đường đi này. Thực tế chúng
co
cũng có thể được gửi đi đồng thời trên nhiều đường
an
th
1Mbps
ng 2Mbps
o
S A B C D
du
3Mbps 3Mbps
u
cu
4Mbps
E F
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Graph (đồ hình)
• graph G=(V, E) được định nghĩa bởi tập hợp các đỉnh
(vertex) V và tập hợp các cạnh E (edge). Các đỉnh thường
om
được gọi là các nút, các cạnh được gọi là các liên kết
.c
ng
• Ký hiệu V={vi | i=1,2,......N}; E={ei | i=1,2,......M}
co
ej=(vi ,vk) hoặc ej=(i,k)
an
th
o ng
du
u
cu
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Định nghĩa
om
.c
ng
co
an
th
• Nút kề nhau (láng giềng): nút i và k gọi là kề nhau nếu tồn tại một liên
ng
kết (i, k) giữa chúng
o
du
• Bậc của nút là số lượng liên kết đi tới nút
u
– Là số lượng nút láng giềng nếu giữa hai nút có không nhiều hơn một liên
cu
kết
• Liên kết có hướng được gọi là cung: ký hiệu: aj=[vi ,vk] hoặc aj=[i, k]
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Định nghĩa
• Graph gọi là vô hướng nếu chỉ chứa các liên kết vô hướng. Nếu chứa ít
nhất một cung, graph được coi là có hướng.
om
– Trong nhiều trường hợp, liên kết vô hướng có thể được xem là tập hợp của
.c
hai liên kết có hướng ngược nhau
ng
• Nếu giữa hai nút, tồn tại hai liên kết tách biệt thì chúng được gọi là các
co
liên kết song song.
an
– Graph có chứa các liên kết song song được gọi là multigraph
th
• Vòng lặp: liên kết nối một nút với chính nó
o ng
• Đường dẫn (path) giữa hai nút là tập hợp các liên kết nối tiếp nhau
du
• Chu trình (cycle): là đường dẫn có điểm đầu và cuối trùng nhau
u
cu
• Graph liên thông (connected graph): giữa hai nút bất kỳ đều tồn tại ít
nhất một đường dẫn
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Định nghĩa
• Graph con (subgraph) G’ của G ?
• Cây (tree): là graph liên thông không chứa chu trình
om
– Định lý: cây N nút luôn có N-1 cạnh
.c
– Nút cha (parent node) của một nút là nút liền kề liên kề và gần nút gốc hơn
ng
– Sao (star): là graph với một nút duy nhất có bậc lớn hơn 1
co
– Xích (chain): là graph mà tất cả các nút đều có bậc không lớn hơn 2
an
th
• Graph có trọng số (weighted graph): mỗi cạnh được gán các con số
ng
thực được gọi là trọng số.
o
du
– Thực tế, trọng số thường trực hoặc gián tiếp biểu đạt một tham số mạng
thông tin như băng thông, chiều dài…gọi là link cost
u
cu
– Định tuyến là việc tìm đường dẫn có tổng link cost nhỏ nhất
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Phân loại định tuyến
om
Định tuyến tĩnh
.c
Flooding
ng
Định tuyến Định tuyến ngẫu nhiên Random walk
co
an
Hot potato
th
ng
Minimum Spanning Tree
Định tuyến động
o
du
Shortest Path Tree
u
cu
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Định tuyến ngẫu nhiên: flooding
• Khi nhận được mỗi gói tin, nút mạng sẽ gửi đi tất cả các nút kế cận, trừ
nút đã gửi gói tin cho nó
om
• Hiệu quả truyền thấp chỉ được áp dụng trong một số ít trường hợp: ví
.c
dụ như quân sự, cập nhật bảng định tuyến
ng
• Đường ngắn nhất nằm trong số các đường đi mà gói tin đi qua: chắc
co
chắn có mẫu gói đi theo đường ngắn nhất
an
th
ng
S A C D
o
du
u
cu
E F
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Định tuyến ngẫu nhiên: random walk
• Gói tin được gửi đến mỗi đầu ra với một xác suất nào đó
• So với flooding, số lượng gói truyền đi nhỏ hơn
om
• Đường đi ngắn nhất có thể không nằm trong số đường được lựa chọn
.c
ng
p
co
an
th
S A ng C D
1-p
o
du
u
cu
B
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Định tuyến ngẫu nhiên: hot potato
• Có tên là isolated adaptive algorithm, tức là việc quyết định tuyến đi dựa
trên trạng thái của chính nút mạng
om
• Gói tin được gửi đến đầu ra có hàng đợi ngắn nhất với mong muốn trễ
.c
sẽ thông tin sẽ nhỏ nhất
ng
• Trễ thực tế chưa chắc đã nhỏ nhất do … ?
co
an
th
o ng
du
u
cu
CuuDuongThanCong.com https://fb.com/tailieudientucntt
nguon tai.lieu . vn
