Tài liệu Báo cáo đồ án mạng viễn thông tìm đường trong chuyển mạch

TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN, ĐHQG – TPHCM KHOA: ĐIỆN TỬ - VIỄN THÔNG CHUYÊN NGÀNH: VIỄN THÔNG - MẠNG  BÁO CÁO ĐỒ ÁN MẠNG VIỄN THÔNG NHÓM 3 ĐỀ TÀI 8: TÌM ĐƯỜNG TRONG CHUYỂN MẠCH GVHD: Th.S TRẦN THỊ HUỲNH VÂN TP.Hồ Chí Minh, tháng 05 năm 2021 DANH SÁCH THÀNH VIÊN NHÓM: 3 STT Họ và tên MSSV 1 Hoàng Bảo Ân(TB) 18200001 2 Nguyễn Minh Nhựt 18200011 3 Tạ Viết Tài(NT;TB) 18200014 4 Trần Viễn Phương 18200036 5 Đoàn Võ Quang Huy 18200121 6 Hà Thị Cẩm Tiên 18200255 Phân công Đánh giá TÌM ĐƯỜNG TRONG CHUYỂN MẠCH MỤC LỤC: LỜI NÓI ĐẦU ............................................................................................................................................. 4 ĐỊNH NGHĨA: .................................................................................................................................... 5 I. 1. Chuyển mạch: .................................................................................................................................. 5 2. Tìm đường trong chuyển mạch:..................................................................................................... 5 PHÂN LOẠI: ................................................................................................................................... 6 II. 1. Chuyển mạch kênh (circuit switching):......................................................................................... 6 2. Chuyển mạch tin (message switching) : ........................................................................................ 7 3. Chuyển mạch gói (packet switching):............................................................................................ 7 4. Một số loại chuyển mạch khác: .................................................................................................... 10 a. Chuyển mạch nhãn đa giao thức (MPLS). .............................................................................. 10 TÌM ĐƯỜNG TRONG CHUYỂN MẠCH: ................................................................................ 11 III. Tìm đường trong chuyển mạch kênh: ......................................................................................... 11 1. a. FHR – Fixed Hierarchical Routing : ....................................................................................... 12 b. DNHR – Dynamic Nonhierarchical Routing : ........................................................................ 14 Tìm đường trong chuyển mạch gói .............................................................................................. 17 2. a. Chức năng: ................................................................................................................................. 17 b. Phân biệt kĩ thuật định tuyến : ................................................................................................ 17 Chiến thuật tìm đường : ............................................................................................................... 18 3. a. Fixed Routing ............................................................................................................................ 18 b. Flooding Routing ....................................................................................................................... 18 c. Random Routing ....................................................................................................................... 18 d. Adaptive Routing....................................................................................................................... 18 Thuật toán: .................................................................................................................................... 19 4. a. Distance Vector Algorithm:...................................................................................................... 19 b. Link State Algorithm: ............................................................................................................... 20 Đánh giá, so sánh:.......................................................................................................................... 21 5. a. Bellman - Ford:.......................................................................................................................... 21 b. Dijkstra: ..................................................................................................................................... 22 QUALITY OF SERVICE (QoS):................................................................................................. 22 IV. Mục tiêu: ........................................................................................................................................ 22 1. a. Đáp ứng đòi hỏi về QoS của các luồng dữ liệu: ...................................................................... 22 b. Tối ưu hệ số sử dụng tài nguyên mạng:................................................................................... 22 c. Hiệu suất mạng không bị giảm đáng kể khi có sự cố xuất hiện như tắc nghẽn: .................. 22 2 TÌM ĐƯỜNG TRONG CHUYỂN MẠCH Các kiểu định tuyến và khó khăn ................................................................................................ 22 2. a. Một số kiểu định tuyến được phát triển .................................................................................. 22 b. Định tuyến hỗ trợ QoS cũng gặp một số khó khăn nhất định:.............................................. 23 Cách tiếp cận bài toán tìm đường: ............................................................................................... 23 3. a. Định tuyến tập trung: ............................................................................................................... 23 b. Định tuyến phân tán: ................................................................................................................ 23 c. Định tuyến phân cấp: ................................................................................................................ 23 Chi phí:........................................................................................................................................... 24 4. V. a. Chi phí giao thức: ...................................................................................................................... 24 b. Chi phí yêu cầu xử lí: ................................................................................................................ 24 c. Chi phí lưu trữ thông tin: ......................................................................................................... 24 ỨNG DỤNG:...................................................................................................................................... 24 TÀI LIỆU THAM KHẢO ........................................................................................................................ 26 3 TÌM ĐƯỜNG TRONG CHUYỂN MẠCH LỜI NÓI ĐẦU Nhiều công trình khoa học ra đời theo thời gian, chất lượng cuộc sống ngày càng cải thiện. Do đó nhu cầu trao đổi thông tin cũng không ngừng tăng. Việc trao đổi thông tin giữa con người ở những khoảng cách khác nhau được đặt ra. Cùng với sự phát triển của khoa học và công nghệ, Mạng viễn thông ra đời và đáp ứng hầu hết những yêu cầu của con người. Việc truyền thoại, số liệu đã trở nên rất đơn giản. Kỹ thuật chuyển mạch là một trong những kỹ thuật mấu chốt trong các mạng truyền thông. Lần này, nhóm chúng em được thử sức với đề tài “Tìm đường trong chuyển mạch” ở bộ môn Mạng viễn thông. Chúng em xin gửi lời cảm ơn đến cô Vân – GV phụ trách bộ môn Mạng viễn thông đã giúp chúng em một phần hoàn thành đề tài này. Tiếp thêm những kiến thức cơ bản quan trọng và bổ ích về chuyên ngành. Trong quá trình tìm hiểu và hoàn thành không tránh những thiếu sót. Vì vậy rất mong nhận được sự góp ý của cô và các bạn. Chúng em xin chân thành cảm ơn. NHÓM 8 4 TÌM ĐƯỜNG TRONG CHUYỂN MẠCH I. ĐỊNH NGHĨA: 1. Chuyển mạch: Chuyển mạch là một quá trình thực hiện đấu nối và chuyển thông tin cho người sử dụng thông qua hạ tầng mạng viễn thông. Nói cách khác, chuyển mạch trong mạng viễn thông bao gồm chức năng định tuyến cho thông tin và chức năng chuyển tiếp thông tin. Quá trình chuyển mạch được thực hiện tại các nút chuyển mạch, trong mạng chuyển mạch kênh thường được gọi là hệ thống chuyển mạch (tổng đài) trong mạng chuyển mạch gói thường được gọi là thiết bị định tuyến (bộ định tuyến). Xét về mặt công nghệ, chuyển mạch chia thành hai loại cơ bản: chuyển mạch kênh và chuyển mạch gói. Mặt khác, chuyển mạch còn được chia ra thành bốn kiểu: chuyển mạch kênh, chuyển mạch bản tin, chuyển mạch gói và chuyển mạch tế bào. 2. Tìm đường trong chuyển mạch: Chuyển mạch trong mạng máy tính giúp quyết định đường tốt nhất để truyền dữ liệu nếu có nhiều đường khác nhau trong một mạng lớn. Cung cấp kết nối one-to-one giữa 2 node đầu và cuối. Yêu cầu: - 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). - 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 hoạt động ở mức độ nào đó trong những trường hợp mạng như vậy. 5 TÌM ĐƯỜNG TRONG CHUYỂN MẠCH II. PHÂN LOẠI: 1. Chuyển mạch kênh (circuit switching): Một đặc trưng nổi bật của kĩ thuật này là hai trạm muốn trao đổi thông tin với nhau thì giữa chúng sẽ được thiết lập một “ kênh” (circuit) cố định, kênh kết nối này được duy trì và dành riêng cho hai trạm cho tới khi cuộc truyền tin kết thúc. Thông tin cuộc gọi là trong suốt. Quá trình thiết lập cuộc gọi tiến hành gồm 3 giai đoạn: - Giai đoạn thiết lập kêt nối: Thực chất quá trình này là liên kết các tuyến giữa các trạm trên mạng thành một tuyến (kênh) duy nhất dành riêng cho cuộc gọi. Kênh này đối với PSTN là 64kb/s (do bộ mã hóa PCM có tốc độ lấy mẫu tiếng nói 8kb/s và được mã hóa 8 bit). - Giai đoạn truyền tin: Thông tin cuộc gọi là trong suốt. Sự trong suốt thể hiện qua hai yếu tố: thông tin không bị thay đổi khi truyền qua mạng và độ trễ nhỏ. - Giai đoạn giải phóng (huỷ bỏ) kết nối: Sau khi cuộc gọi kết thúc, kênh sẽ được giải phóng để phục vụ cho các cuộc gọi khác. Qua đó, ta nhận thấy mạng chuyển mạch kênh có những ưu điểm nổi bật như chất lượng đường truyền tốt, ổn định, có độ trễ nhỏ. Các thiết bị mạng của chuyển mạch kênh đơn giản, có tính ổn định cao, chống nhiễu tốt. Nhưng ta cũng không thể không nhắc tới những hạn chế của phương thức truyền dữ liệu này như: - Sử dụng băng thông không hiệu quả: Tính không hiệu quả này thể hiện qua hai yếu tố. Thứ nhất, độ rộng băng thông cố định 64k/s. Thứ hai là kênh là dành riêng cho một cuộc gọi nhất định. Như vậy, ngay cả khi tín hiệu thoại là “lặng” (không có dữ liệu) thì kênh vẫn không được chia sẻ cho cuộc gọi khác. - Tính an toàn: Do tín hiệu thoại được gửi nguyên bản trên đường truyền nên rất dễ bị nghe trộm. Ngoài ra, đường dây thuê bao hoàn toàn có thể bị lợi dụng để ăn trộm cước viễn thông. - Khả năng mở rộng của mạng kênh kém: Thứ nhất là do cơ sở hạ tầng khó nâng cấp và tương thích với các thiết bị cũ. Thứ hai, đó là hạn chế của hệ thống báo hiệu vốn đã được sử dụng từ trước đó không có khả năng tùy biến cao. 6 TÌM ĐƯỜNG TRONG CHUYỂN MẠCH 2. Chuyển mạch tin (message switching) : - Là loại phục vụ sự trao đổi thông tin giữa các bản tin như điện tín, thư điện tử. Thiết bị đầu cuối gửi đến node chuyển mạch các thông tin về địa chỉ. Tại đây, bản tin được thu nhận, xử lý rồi chờ được chuyển đi. Thông tin được gửi đi như một đơn vị đầy đủ và chuyển tiếp tại các node trung chuyển bằng store and forward mechanism. Không phù hợp cho streaming media và các ứng dụng thời gian thực do các bản tin sau khi được tiếp nhận phải chờ mới được chuyển đi. 3. Chuyển mạch gói (packet switching): Trong chuyển mạch gói mỗi bản tin được chia thành các gói tin (packet), có khuôn dạng được quy định trước. Trong mỗi gói cũng có chứa thông tin điều khiển: địa chỉ trạm nguồn, địa chỉ trạm đích và số thứ tự của gói tin,… Các thông tin điều khiển được tối thiểu, chứa các thông tin mà mạng yêu cầu để có thể định tuyến được cho các gói tin qua mạng và đưa nó tới đích. Tại mỗi node trên tuyến gói tin được nhận, nhớ và sau đó thì chuyển tiếp cho tới chạm đích. Vì kỹ thuật chuyển mạch gói trong quá trình truyền tin có thể được định tuyến động để truyền tin. Điều khó khăn nhất đối với chuyển mạch gói là việc tập hợp các gói tin để tạo bản tin bản đầu đặc biệt là khi mà các gói tin được truyền theo nhiều con đường khác nhau tới trạm đích. Chính vì lý do trên mà các gói tin cần phải được đánh dấu số thứ tự, điều này có tác dụng, chống lặp, sửa sai và có thể truyền lại khi hiên tượng mất gói xảy ra. Các ưu điểm của chuyển mạch gói: - Mềm dẻo và hiệu suất truyền tin cao: Hiệu suất sử dụng đường truyền rất cao vì trong chuyển mạch gói không có khái niệm kênh cố định và dành riêng, mỗi đường truyền giữa các node có thể được các trạm cùng chia sẻ cho để truyền tin, các gói tin sắp hàng và truyền theo tốc độ rất nhanh trên đường truyền. - Khả năng truyền ưu tiên: Chuyển mạch gói còn có thể sắp thứ tự cho các gói để có thể truyền đi theo mức độ ưu tiên. Trong chuyển mạch gói số cuộc gọi bị từ chối ít hơn nhưng phải chấp nhận một nhược điểm vi thời gian trễ sẽ tăng lên. - Khả năng cung cấp nhiều dịch vụ thoại và phi thoại. - Thích nghi tốt nếu như có lỗi xảy ra: Đặc tính này có được là nhờ khả năng định tuyến động của mạng. Bên cạnh những ưu điểm thì mạng chuyển mạch gói cũng bộc lộ những nhược điểm như: - Trễ đường truyền lớn: Do đi qua mỗi trạm, dữ liệu được lưu trữ, xử lý trước khi được truyền đi. - Độ tin cậy của mạng gói không cao, dễ xảy ra tắc nghẽn, lỗi mất bản tin. - Tính đa đường có thể gây ra lặp bản tin, làm tăng lưu lượng mạng không cần thiết. 7 TÌM ĐƯỜNG TRONG CHUYỂN MẠCH - Tính bảo mật trên đường truyền chung là không cao. a) Datagram: Trong phương pháp này, mỗi gói được xử lý độc lập. Ngay cả khi một gói là một phần của cuộc truyền nhiều gói đi nữa thì mạng (và các chức năng lớp mạng) đều xử lý chúng như là đơn lẻ. Phương pháp này được gọi là datagram. Hình dưới đây cho thấy hướng datagram có thể dùng để chuyển giao 4 gói từ trạm A đến trạm X. Trong ví dụ này, tất cả bốn gói (hay datagram) đều thuộc về cùng một bản tin nhưng có thể đi đến đích bằng nhiều đường dẫn khác nhau. Tuy nhiên phương pháp này có thể làm cho các gói đến đích không theo thứ tự, điều này yêu cầu lớp vận chuyển trong hầu hết các giao thức để sắp xếp lại trước khi đi đến đích. Kết nối liên kết mỗi cặp của nút có thể gồm nhiều kênh. Mỗi kênh này lại có thể mang datagram từ một hay nhiều nguồn khác nhau. Phương pháp đa hợp có thể dùng là TDM hay FDM. Một số đường trong mạng có thể chỉ dùng một kênh trong khi đường khác thì dùng nhiều kênh. b) Chuyển mạch ảo: Kênh ảo (VC: Virtual Circuit) là phương tiện truyền dữ liệu qua mạng chuyển mạch gói theo cách mà nó có vẻ như có một liên kết vật lý chuyên dụng giữa nguồn và đích hệ thống cuối của dữ liệu này. Thuật ngữ mạch ảo đồng nghĩa với kết nối ảo. 8 TÌM ĐƯỜNG TRONG CHUYỂN MẠCH Trước khi kết nối hoặc mạch ảo có thể được sử dụng, nó phải được thiết lập giữa hai hoặc nhiều nút hoặc ứng dụng phần mềm . Sau đó, luồng bit hoặc luồng byte có thể được phân phối giữa các nút. - Nối kết logic của kênh truyền được thiết lập trước khi truyền các gói gọi là kênh ảo VC. - Giống như chuyển mạch kênh và kênh ảo sẽ được giải phóng khi kết thúc quá trình chuyển tin. Cùng một thời gian thì một PSE có thể có nhiều VC đến một PSE khác. PSE: Packet Switching Exchange (Tổng đài chuyển mạch gói); Kênh ảo vĩnh viễn PVC (Permanent Virtual Circuit): - PVC là phương thức thiết lập kênh ảo cố định giữa hai thuê bao cho dù có truyền dữ liệu hay không. - PVC có thể được xem như việc thuê kênh riêng, trong kiểu này thì kênh dẫn được thiết lập một lần ở thời điểm khởi tạo và sẽ được giải phóng khi hết nhu cấu sử dụng dịch vụ (hợp đồng). Giao tiếp mạch ảo tương tự như chuyển mạch kênh, vì cả hai đều là định hướng kết nối, nghĩa là trong cả hai trường hợp, dữ liệu được phân phối theo đúng thứ tự và chi phí báo hiệu là cần thiết trong giai đoạn thiết lập kết nối. Tuy nhiên, chuyển mạch kênh cung cấp tốc độ bit và độ trễ không đổi, trong khi những tốc độ này có thể khác nhau trong dịch vụ mạch ảo do các yếu tố như: - Độ dài hàng đợi gói khác nhau trong các nút mạng. - Tốc độ bit khác nhau được tạo ra bởi ứng dụng. - Tải khác nhau từ những người dùng khác chia sẻ cùng tài nguyên mạng bằng phương pháp ghép kênh thống kê , v.v. Mạch ảo lớp 4: Các giao thức lớp truyền tải định hướng kết nối như TCP có thể dựa vào giao thức lớp mạng chuyển mạch gói không kết nối như IP , nơi các gói khác nhau có thể được định tuyến qua các đường dẫn khác nhau, và do đó được giao không theo đơn đặt hàng. Tuy nhiên, có thể sử dụng TCP như một mạch ảo, vì TCP bao gồm việc đánh số phân đoạn cho phép sắp xếp lại thứ tự ở phía người nhận để đáp ứng việc phân phối không theo thứ tự. Mạch ảo lớp 2/3: Lớp liên kết dữ liệu và lớp mạng các giao thức mạch ảo dựa trên chuyển mạch gói hướng kết nối , nghĩa là dữ liệu luôn được phân phối dọc theo cùng một đường dẫn mạng, tức là qua các nút giống nhau. Ưu điểm của việc này so với chuyển mạch gói không kết nối là: Hỗ trợ: - Bảo lưu băng thông trong giai đoạn thiết lập kết nối, làm cho chất lượng dịch vụ (QoS) được đảm bảo. Ví dụ, một lớp QoS tốc độ bit không đổi có thể được cung cấp, dẫn đến mô phỏng chuyển mạch kênh . - Yêu cầu ít chi phí hơn vì các gói không được định tuyến riêng lẻ và thông tin địa chỉ hoàn chỉnh không được cung cấp trong tiêu đề của mỗi gói dữ liệu. Chỉ cần một mã 9 TÌM ĐƯỜNG TRONG CHUYỂN MẠCH định danh kênh ảo (VCI) nhỏ trong mỗi gói. Thông tin định tuyến chỉ được chuyển đến các nút mạng trong giai đoạn thiết lập kết nối. - Các nút mạng nhanh hơn và có dung lượng cao hơn về lý thuyết vì chúng là các thiết bị chuyển mạch chỉ thực hiện định tuyến trong giai đoạn thiết lập kết nối, trong khi các nút mạng không kết nối là các bộ định tuyến thực hiện định tuyến cho từng gói tin riêng lẻ. Việc chuyển đổi chỉ liên quan đến việc tra cứu mã nhận dạng kênh ảo trong bảng chứ không phải phân tích một địa chỉ hoàn chỉnh. Việc chuyển mạch có thể dễ dàng thực hiện trong phần cứng ASIC , trong khi việc định tuyến phức tạp hơn và yêu cầu thực hiện phần mềm. Tuy nhiên, do thị trường bộ định tuyến IP rộng lớn và vì bộ định tuyến IP tiên tiến hỗ trợ chuyển mạch lớp 3 , bộ định tuyến IP hiện đại ngày nay có thể nhanh hơn bộ chuyển mạch cho các giao thức hướng kết nối. 4. Một số loại chuyển mạch khác: a. Chuyển mạch nhãn đa giao thức (MPLS). Chuyển mạch nhãn đa giao thức là công nghệ đưa ra phương thức cải tiến cho việc chuyển tiếp gói tin qua mạng. MPLS là sự kết hợp giữa kỹ thuật định tuyến lớp 3 và chuyển mạch lớp 2 cho phép nâng cao tốc độ chuyển tiếp lưu lượng trên mạng lõi và định tuyến tốt ở mạng biên bằng cách gắn thêm nhãn vào các gói tin. Vị trí và dạng của nhãn tùy thuộc vào giao thức truyền tải ở lớp 2. Mục tiêu của MPLS là tạo ra một cấu trúc mạng có tính mềm dẻo có thể mở rộng và tạo sự ổn định của mạng. VD minh họa: 10 TÌM ĐƯỜNG TRONG CHUYỂN MẠCH Các gói tin khi đến biên của mạng MPLS thì router A thực hiện phân nhóm, gán nhãn cho gói tin và xác định đường đi xuyên qua mạng. Các router B và router C thực hiện việc thay đổi giá trị của nhãn và chuyển tiếp gói tin. Router biên D gỡ bỏ nhãn ra khỏi gói tin. Các router trong mạng như B và C không kiểm tra toàn bộ header mà chỉ dựa vào thông tin của nhãn và thông tin duy trì tại mỗi node mạng để chuyển gói tin. Nên tốc độ xử lý trong miền MPLS sẽ nhanh hơn rất nhiều so với định tuyến IP theo từng chặng đường truyền thống. III. TÌM ĐƯỜNG TRONG CHUYỂN MẠCH: 1. Tìm đường trong chuyển mạch kênh: Tìm đường trong chuyển mạch kênh là quá trình xác định đường đi giữa các node mạng đảm bảo tối ưu về mặt kinh tế và kỹ thuật của mạng. Nó phải thỏa yêu cầu trong các quá trình định tuyến như: không có vòng lặp giữa các node mạng, thủ tục điều khiển đơn giản, quản lý thiết bị thích ứng được với các điều kiện mạng thay đổi trong quá trình sử dụng. Có hai phương pháp cơ bản thường sử dụng trong mạng chuyển mạch kênh phân chia dựa trên thuộc tính động là định tuyến động và định tuyến tĩnh. Định tuyến tĩnh Định tuyến động - Không quan tâm đến trạng thái kênh - Tự động phản ứng lại với thay đổi trong truyền của mạng hay thay đổi trong ma trận lưu lượng tải, ma trận định tuyến và tình định tuyến. trạng mạng. - Mặc định tính đến trạng thái của các - Phản ứng lại với kết nối và node bị lỗi nguồn khác. + Tăng tiêu tốn tài nguyên khi phải thu thập + Dễ dàng thu được thông tin của các thông tin của các node xa. nguồn lân cận. + Các node sẽ theo dõi và khi kênh bị khóa thì sẽ chuyển kênh khác nhưng không có giao thức rõ ràng như trong IP (Internet Protocols). - Hữu ích khi có nhiều đường thay thế. 11 TÌM ĐƯỜNG TRONG CHUYỂN MẠCH a. FHR – Fixed Hierarchical Routing : Hầu hết các biến thể của tìm đường luân phiên tĩnh dùng trong mạng PSTN Nút chuyển tiếp Tuyến dựa)phòng Trung kế Nút B Nút A Tuyến trực tiếp Nút C Các chuyển mạch được kết nối theo cấu trúc phân cấp – Fixed Hierachical (thường là hình cây). Thiết kế các đường trunk nối ngang cấu trúc cây để cung cấp các đường thay thế. Như trong hình gọi là định tuyến luân phiên tĩnh vì mỗi một tuyến đường thì số kênh được khai báo sử dụng là cố định và được tính toán trên kết quả dự báo lưu lượng. Nên nếu kết quả dự báo sai thì sẽ dẫn đến hai khả năng: + Lưu lượng bị tổn thất nhiều dẫn đến chất lượng dịch vụ không cao. + Số kênh bị thừa nhiều thì dẫn đến hiệu quả sử dụng kênh không cao Thuật toán trong FHR: 12 TÌM ĐƯỜNG TRONG CHUYỂN MẠCH Các quy tắc cơ bản của FHR : + Lựa chọn đường đi chỉ dựa trên số gọi ( từ thiết bị đầu cuối). Nơi gọi không bị ảnh hưởng. + Một node luôn lựa chọn nhóm kênh khả dụng đầu tiên để cung cấp cho cuộc gọi. + Các đường thay thế được sắp xếp theo thứ tự khoảng cách phân tầng tăng dần từ node gần nhất đến node thiết bị đầu cuối. + Đường thay thế cuối cùng luôn dùng nhóm trunk cuối. Nếu không có các kênh rảnh thậm chí trong nhóm trunk cuối thì cuộc gọi sẽ bị khóa. Đặc điểm của FHR: + Sử dụng SOC (Sequential Office Control) giúp kiểm soát sự tuần tự không bị xung đột cuộc gọi nội bộ. + Vòng lặp không xảy ra + Chia các node thành các thiết bị đầu cuối và các thiết bị trung chuyển tiện cho việc quản lí. + Không sử dụng hiệu quả tài nguyên mạng. 13 TÌM ĐƯỜNG TRONG CHUYỂN MẠCH b. DNHR – Dynamic Nonhierarchical Routing : Tất cả các kết nối đều ngang hàng – không có sự phân tầng. Một nhóm kênh có thể là lựa chọn cuối cho một vài cuộc gọi và không là lựa chọn cuối của các cuộc gọi khác. Độ dài của các đường thay thế là 2 hop : + Không bị vòng lặp. + Tránh việc các đường thay thế dài sẽ có vấn đề khi bị quá tải trên mạng. Dùng hệ thống các bảng định tuyến, mỗi bảng sẽ được chọn dựa trên thời gian trong ngày. Dùng OOC ( Origianl Office Control) và crankback. Tạo và tối ưu hóa các bảng định tuyến yêu cầu thu thập dữ liệu đường đi tập trung. 14 TÌM ĐƯỜNG TRONG CHUYỂN MẠCH c. DAR – Dynamic Alternative Routing : DAR hoạt động trong mạng dạng lưới hoàn toàn (full mesh). Đường đi trực tiếp từ node i đến node j và các đường thay thế có tối đa 2 hop được sử dụng. Với k(i,j) – node thay thế gần nhất cho việc truyền thông từ node i đến node j, 𝑟𝑖𝑗 là tham số kết nối i,j. Một cuộc gọi từ node i đến node j luôn luôn dùng kênh trực tiếp nếu kênh sẵn sàng. Nếu không, cuộc gọi sẽ dùng đường thay thế có 2 hop qua node k. Cuộc gọi thành công nếu 𝑟𝑖𝑘 và 𝑟𝑘𝑗 khả dụng. Nếu không, cuộc gọi sẽ bị khóa và lựa chọn một node k mới. Đặc điểm của DAR : + Một cuộc gọi dùng đường thay thế 2 hop có thể gây ra chặn cả các cuộc gọi đến sau nếu nó được phép dự trữ kênh cuối cùng. + Không có tham số kết nối 𝑟𝑖𝑗 thì trạng thái của mạng sẽ không ổn định – số lượng tối đa các kết nối thay thế thông qua giữa các mức độ tạo ra dao động mạng. + Trên các kết nối dung lượng lớn thì r cũng là giá trị nhỏ. Thậm chí mặc định là r≠0 trên đường thay thế đầu tiên. + Nếu một cuộc gọi được phép thử truyền thêm trên một kênh truyền thay thế 2 hop, giá trị của r phải tăng. + Một số đường thay thế tốt hơn các đường thay thế khác nên sẽ ưu tiên được chọn. Nếu truyền thông trên một kênh thay thế tăng mạnh thì nó có thể phân tán ra một vài kênh truyền thay thế gần đó. Ví dụ: Có N node, N(N-1) kết nối, mỗi kết nối có M kênh. Mỗi node phát sinh p cuộc gọi thì : + Nếu các cuộc gọi chỉ dùng kết nối trực tiếp => pN ≤ N(N-1)M => p ≤ (N-1)M + Nếu các cuộc gọi đều dùng kết nối kênh truyền 2 hop : tổng cộng có 2pN kênh truyền => 2pN ≤ N(N-1)M => p ≤ (N-1)M/2. 15 TÌM ĐƯỜNG TRONG CHUYỂN MẠCH d. RCAR – Residual Capacity Adaptive Routing: - Cải thiện hiệu suất mạng đáng kể Đáp ứng nhanh với các kiểu hình truyền thông khác thường và với các kết nối hay node bị lỗi. Lợi ích liên quan đến sự khác biệt thời gian giữa các biên. Dễ lỗi đối với trung tâm quản lí. Sẽ trả về dạng FHR nếu trung tâm quản lí bị lỗi. e. RTNR – Real-time Network Routing : - Dùng trong mạng AT&T từ 1991. Là kế thừa của mạng DNHR. 16 TÌM ĐƯỜNG TRONG CHUYỂN MẠCH Nguồn node i trước hết thử kết nối trực tiếp đến đích j. Nếu kết nối trực tiếp không sẵn sàng, hỏi trạng thái điểm đích để tìm ra node phụ k. Việc xếp hàng có thể là nguyên nhân gây trì hoãn trong việc thiết lập kết nối. Có thể dùng các kết quả để xếp trước đó, sắp xếp và lưu vào cache cho các cuộc gọi kế tiếp. Cần crankback. - f. Tổng kết về tìm đường trong chuyển mạch kênh: Định tuyến tĩnh là phổ biến nhất trong PSTN. Định tuyến luân phiên dễ dàng như một lẽ tự nhiên khi cuộc gọi đang diễn ra giữ nguyên kênh truyền và cuộc gọi mới tìm một đường thay thế khác. Định tuyến động với thông tin nội bộ thường đạt được tỉ lệ bị khóa thấp giống như định tuyến theo tải cần thông tin toàn cục. - 2. Tìm đường trong chuyển mạch gói Mục tiêu cơ bản của các phương pháp định tuyến là nhằm sử dụng tối đa tài nguyên mạng, tối ưu giá thành mạng và phải đạt được các yêu cầu như: Chính xác, đơn giản, tính mạnh mẽ, ổn định, công bằng với tối ưu và phải sử dụng một cách hiệu quả. a. Chức năng: - Quyết định chọn đường theo một tiêu chuẩn tối ưu nào đó + Số chặng đường (hopcount) là tối thiểu + Chi phí (cost) là tối thiểu Mỗi một đường dẫn có một chi phí khác nhau Chi phí có thể là: Data rate hay delay (do các gói phải xếp hàng chờ được chuyển). - Cập nhập thông tin định tuyến (thông tin dùng cho chức năng) b. Phân biệt kĩ thuật định tuyến : - Thời điểm và nơi quyết định tìm đường: + Thời điểm: Trên cơ sở mạch ảo hoặc mạch gói Datagram quyết định thực hiện riêng cho mỗi gói Virtual circuit quyết định đưa ta lúc kết nối + Nơi quyết định: Có thể là phân tán (distributed), tập trung (centralized) hay là tại nguồn (source) - Nguồn thông tin mạng và thời điểm cập nhập thông tin: Các quyết định tìm đường thường được dựa trên các thông tin trên mạng như: tải lưu thông hay chi phí của đường đi. Cần phải các định thời điểm cập nhập các thông tin mạng được lưu trữ ở các node như: không bao giờ cập nhập (fixed), cập nhập thường xuyên (adaptive) hay trade off. 17 TÌM ĐƯỜNG TRONG CHUYỂN MẠCH 3. Chiến thuật tìm đường : a. 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ập lại các biến đổi trong mạng. - Đường đi được xác định theo 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 nhau giữa datagram và virtual circuit. - Đơn giản nhưng không đáp ứng lỗi và nghẽn mạng. b. Flooding Routing - Không cần thông tin mạng - Node gửi broadcast đến các node láng giềng. - Các gói nhận được sẽ truyền trên tất cả các đường khác trừ đường truyền đến. - Chắc chắn sẽ có một số copy của gói truyền đến đích, các copy được đánh số nên những gói trùng nhau sẽ bị bỏ. - Node ghi nhớ các gói đã đi qua, nên mạng không cần tải quá nhiều. - Số chặng đường (hopcount) được chứa trong các gói dùng để giới hạn lại quá trình truyền. → Dùng để gửi các tin khẩn, thiết lập Virtual circuit và gửi broadcast thông tin. c. Random Routing - Node sẽ chọn ngẫu nhiên hoặc xoay vòng ra một đường để truyền các gói nhận được - Không cần thông tin mạng - Đường được chọn thường không phải là đường có chi phí thấp nhất vì việc chọn là ngẫu nhiên. d. Adaptive Routing - Isolated Adaptive Routing: + Mỗi node trong mạng tự cập nhập 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 nhưng có thể không đúng với hướng cần đi. + Có thể thêm độ ưu tiên (bias) cho các đường ra. + 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. 18 TÌM ĐƯỜNG TRONG CHUYỂN MẠCH - Distributed Adaptive Routing: + Thông tin về tình trạng hoạt động hiện hành của mạng sẽ được định kỳ trao đổi, cập nhập giữa các node trong toàn mạng. Sau đó thông tin này đượ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ập lại bảng định tuyến. + Đáp ứng được với những thay đổi trạng thái trong mạng mà không làm tăng lưu lượng thông tin trong mạng. - 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ập giữa các node trong toàn mạng. Sau đó thông tin này được tập trung về một máy chủ trong mạng làm nhiệm vụ định tuyến. + Phương pháp này đáp ứng được những thay đổi tức thời trong mạng nhưng tất cả các thông tin định tuyến đều tập trung về máy chủ nên khi máy chủ có vấn đề thì toàn mạng sẽ không hoạt động được. 4. Thuật toán: Có 2 loại thuật toán được dùng phổ biến trong định tuyến động là: thuật toán định tuyến theo vector khoảng cách DVA ( Distance Vector Algorithm) và thuật toán định tuyến theo trạng thái liên kết LSA ( Link State Algorithm). a. Distance Vector Algorithm: Là thuật toán định tuyến con đường ngắn nhất giữa các cặp node mạng, dựa trên phương pháp tập trung được biết đến như là thuật toán Bellman-Ford. Các node mạng thực hiện quá trình trao đổi thông tin trên cơ sở của địa chỉ đích, node kế tiếp và con đường ngắn nhất đến đích. 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ố - 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 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. dij : Trọng số trên cạnh nối từ node i đến node j. Giải thuật: - Bước 1: Khởi động D(1)N = dSN ∀ N∈V\{S} (đường đi ngắn nhất từ S đến N có tối đa 1 đoạn) - Bước 2: Cập nhập đường đi ngắn nhất D(h+1)N = min{ D(h)j + djN} ∀ j∈V\{S} 19