intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Kỹ thuật truyền số liệu - Chương 8: Tìm đường trong mạng chuyển mạch

Chia sẻ: Minh Anh | Ngày: | Loại File: PDF | Số trang:39

Thêm vào BST
Báo xấu
97
lượt xem 9
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Kỹ thuật truyền số liệu - Chương 8: Tìm đường trong mạng chuyển mạch" cung cấp cho người đọc các kiến thức: Tìm đường trong mạng chuyển mạch mạch, tìm đường trong mạng chuyển mạch gói, các giải thuật tìm đường đi ngắn nhất. Hi vọng đây sẽ là một tài liệu hữu ích dành cho các bạn sinh viên Công nghệ thông tin dùng làm tài liệu tham khảo phục vụ học tập và nghiên cứu.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Kỹ thuật truyền số liệu - Chương 8: Tìm đường trong mạng chuyển mạch

  1. dce 2008 Chương 8 Tìm đường trong mạng chuyển mạch Tìm đường trong mạng chuyển mạch mạch BK TP.HCM Tìm đường trong mạng chuyển mạch gói Các giải thuật tìm đường đi ngắn nhất
  2. dce 2008 Tìm đường trong mạng chuyển mạch mạch • Tìm đường – Tìm đường đi kết nối qua mạng giữa 2 node đầu cuối sao cho mạng được sử dụng hiệu quả nhất • Chức năng – Xác định kết nối từ thuê bao gọi đến thuê bao được gọi qua một loạt các chuyển mạch và trung kế • Các yêu cầu đặt ra trong vấn đề tìm đường – Hiệu quả • Xử lý được tải trên mạng vào giờ cao điểm • Giảm thiểu số lượng thiết bị trong mạng (node và trunk) – Khả năng co giãn • Có những trường hợp lưu thông trên mạng vượt quá tải đã thiết kế • Mạng phải đảm bảo khả năng hoạt động ở một mức độ nào đó trong những trường hợp như vậy Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 2
  3. dce 2008 Tìm đường phân cấp • Static Hierachical Routing • Các chuyển mạch được kết nối theo cấu trúc phân cấp (thông thường theo cấu trúc cây) – Đường đi được hình thành từ node lá đi lên • Tăng tính co giãn – Các trung kế (trunk) được kết nối thêm vào cắt ngang cấu trúc cây – Cung cấp các đường đi thay thế • Tĩnh – Không thích nghi theo các điều kiện thay đổi trên mạng – Mạng phải được thiết kế để chịu được tải nặng  oversize – Cấu trúc tĩnh đáp ứng kém với lỗi Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 3
  4. dce 2008 Tìm đường phân cấp FINAL Regional center FINAL HU (high-usage trunks) Sectional center FINAL Primary center FINAL Toll center Alternate Toll connecting Hierarchical Local (End) office tandem Routing switch Telephone Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 4
  5. dce 2008 Tìm đường động • Tìm đường động (Dynamic Routing) – Cho phép thay đổi trong việc tìm đường tùy theo lưu thông trong mạng – Dùng cấu trúc ngang cấp cho các node trong mạng – Đường đi thiết lập giữa hai thuê bao thay đổi tùy theo khả năng tải và băng thông của đường truyền tại thời điểm thiết lập kết nối – Phức tạp và linh động hơn • Một số phương pháp tìm đường động – Dựa vào thống kê biến động trong mạng (tải, băng thông, ...) theo thời gian, còn gọi là Time-dependent Routing • Alternate routing – Dựa vào biến động trong mạng (tải, băng thông, ...) để trao đổi cập nhật thông tin tìm đường đi giữa các node trong mạng, từ đó tìm ra được đường đi tối ưu và cập nhật vào bảng routing ở các node chuyển mạch trong mạng, còn gọi là State-dependent Routing • Adaptive routing – Kết hợp cả hai phương pháp này Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 5
  6. dce 2008 Alternate routing • Các đường đi có thể giữa 2 trạm (end office) được liệt kê trước • Bộ chuyển mạch nguồn chọn lựa các đường thích hợp • Các đường được liệt kê theo thứ tự ưu tiên – Ưu tiên kết nối trực tiếp – Thứ tự ưu tiên dựa vào thống kê lưu thông trên mạng – Fixed alternate routing • Thay đổi thứ tự ưu tiên của các đường đi theo từng thời điểm khác nhau – Dynamic alternate routing Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 6
  7. dce 2008 Tìm đường trong mạng chuyển mạch gói • Vấn đề phức tạp, quyết định đối với mạng chuyển mạch gói • Các đặc tính yêu cầu – Chính xác – Đơn giản – Mạnh mẽ (robustness) • Khả năng chuyển các gói trong điều kiện lỗi và quá tải • Không mất gói hoặc không làm đứt virtual circuit – Ổn định • Hệ thống có khả năng thay đổi theo điều kiện mạng thường có xu hướng không ổn định và đáp ứng chậm • Congestion oscillation – Công bằng vs. tối ưu • Một số hệ thống ưu tiên chuyển các gói đến trạm gần hơn • Tối ưu thông lượng nhưng không công bằng – Hiệu quả • Tìm đường đòi hỏi phải tăng cường xử lý và tăng cường lưu thông trên mạng • Chi phí cho tìm đường phải ít hơn lợi ích (ví dụ tăng tính mạnh mẽ, công bằng) Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 8
  8. dce 2008 Tiêu chuẩn đo tính hiệu quả • Là tiêu chuẩn được dùng để chọn đường – Số chặng đường (hop) là tối thiểu • Đơn giản • Tối thiểu việc sử dụng tài nguyên – Chi phí (cost) tối thiểu • Mỗi đường link được gán một chi phí • Chi phí có thể là – Data rate (tỉ lệ nghịch) – Delay do các gói xếp hàng (tỉ lệ thuận) Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 9
  9. dce 2008 Chi phí các đường đi Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 10
  10. dce 2008 Thời điểm và nơi quyết định việc tìm đường • Thời điểm quyết định – Trên cơ sở mạch ảo hoặc gói – Datagram: quyết định tìm đường thực hiện riêng cho mỗi gói – Virtual circuit: quyết định tìm đường thực hiện lúc kết nối • Trong nhiều thiết kế, đường đi của mỗi virtual circuit thay đổi theo điều kiện của mạng • Nơi quyết định – Node nào sẽ ra quyết định tìm đường – Phân tán (Distributed) • Mỗi node tự ra quyết định tìm đường – Tập trung (Centralized) • Nhiệm vụ tìm đường được gán trước cho 1 số node – Tại nguồn gởi (Source) • Nguồn gởi chịu trách nhiệm tìm đường • Cho phép người dùng chọn đường đi theo tiêu chí của họ Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 11
  11. dce 2008 Nguồn thông tin mạng và thời điểm cập nhật thông tin • 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ải lưu thông – Chi phí của đường link • 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 • Cập nhật thông tin – Xác định khi nào các thông tin mạng được lưu trữ tại các node được cập nhật – Cố định (Fixed) – không bao giờ được cập nhật – Động (Adaptive) – cập nhật thường xuyên – Trade off Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 12
  12. dce 2008 Chiến thuật tìm đường • Chiến thuật (Routing Strategies) – Fixed routing – Flooding routing – Random routing – Adaptive routing Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 13
  13. dce 2008 Fixed Routing • Một lộ trình cố định cho mỗi đường đi từ nguồn đến đích • Tất cả các đường đi qua mạng đều đã được thiết lập từ trước và không cập nhật theo các biến đổi về các điều kiện tải, … trong mạng • Đường đi được xác định dùng giải thuật chi phí tối thiểu • Đường cố định ít ra cho đến khi có sự thay đổi cấu hình mạng • Không có sự khác biệt giữa datagram và VC • Đơn giản • Không đáp ứng lại lỗi và nghẽn mạng Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 14
  14. dce 2008 Flooding Routing • Không cần thông tin mạng • Node gởi các gói tới tất cả node kề (láng giềng) • 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 đến • Cuối cùng sẽ có một số copy của gói sẽ đến đích • Mỗi gói được đánh số duy nhất sao cho các copy trùng nhau sẽ bị loại bỏ • Node có thể ghi nhớ các gói đã đi qua, giúp cho mạng không quá tải nhiều • Có thể chứa số chặng đường (hop) trong các gói, được dùng để giới hạn hay kết thúc quá trình truyền Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 15
  15. dce 2008 Flooding Routing • Đặc điểm – Tất cả các lộ trình đều được thử • Robust • Lãng phí băng thông – Í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 được “duyệt” • Dùng để phân tán thông tin – Gửi các mesg khẩn • Mạng quân sự – Thiết lập VC – Broadcast thông tin Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 16
  16. dce 2008 Random Routing • Node sẽ chọn một đường liên kết ra để truyền đi các gói nhận được • 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 R Pi = i ∑Ri i • Không cần thông tin mạng • 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 Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 17
  17. dce 2008 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 – Hư hỏng (Failure): một node hoặc một trunk hư – Nghẽn (Congestion) • Cần biết các thông tin về mạng • Quyết định tìm đường là một hàm phức tạp • Tradeoff giữa chất lượng của thông tin mạng và chi phí • Phản ứng quá nhanh có khả năng gây dao động • Quá chậm dẫn đến không còn thích hợp Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 18
  18. dce 2008 Adaptive Routing • Ưu điểm – Hiệu suất được cải thiện – Trợ giúp điều khiển nghẽn mạng • Cân bằng tải, tránh tắc nghẽn – Hệ thống phức tạp để hiện thực • Có khả năng không thực hiện các ích lợi về mặt lý thuyết • Phân loại – Dựa trên các nguồn thông tin • Cục bộ (isolated) • Các node kề (distributed) • Tất cả các node (centralized) Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 19
  19. dce 2008 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 routing với các node khác • Gởi các gói trên các liên kết ra có hàng đợi ngắn nhất – Cân bằng tải trên các đường ra – Đường ra có hàng đợi ngắn nhất có thể không đúng hướng cần đi • Có thể thêm các độ thiên vị (bias) cho các đường ra • Một trong những phương pháp đơn giản nhất của tìm đường động, phù hợp với các mạng có kích thước nhỏ và hoạt động tương đối ổn định • Ít dùng (không dùng thông tin có sẵn) Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 20
  20. dce 2008 Isolated Adaptive Routing • Ví dụ • Đường ra được chọn là đường ra có Q+Bi nhỏ nhất Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 21
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
4=>1