Bài giảng Cơ sở truyền số liệu: Chương 4 - ĐH Bách Khoa Hà Nội

Bài giảng này cung cấp cho người học những kiến thức cơ bản về định tuyến trong mạng viễn thông. Những nội dung chính được trình bày trong chương này gồm có: Graph (đồ hình), phân loại định tuyến, định tuyến ngẫu nhiên: flooding, định tuyến ngẫu nhiên: random walk, định tuyến ngẫu nhiên: hot potato.
Nội dung trích xuất từ tài liệu:
Bài giảng Cơ sở truyền số liệu: Chương 4 - ĐH Bách Khoa Hà Nội 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à ...