Đề tài Định tuyến bước sóng

CHƯƠNG 1: HỆ THỐNG THÔNG TIN QUANG DWDM 1.1. NGUYÊN LÝ GHÉP KÊNH THEO BƯỚC SÓNG WDM 1.2. CHUYỂN MẠCH QUANG TRONG HỆ THỐNG DWDM 1.1. NGUYÊN LÝ GHÉP KÊNH THEO BƯỚC SÓNG WDM Giới thiệu hệ thống ghép kênh theo bước sóng WDM Các kết cấu cơ bản của hệ thống DWDM Nguyên lý hoạt động của hệ thống DWDM Giới thiệu hệ thống ghép kênh theo bước sóng WDM Ghép kênh theo bước sóng WDM là công nghệ “trong một sợi quang đồng thời truyền dẫn nhiều bước sóng tín hiệu quang”. Ở đầu phát, nhiều tín hiệu quang có bước sóng khác nhau được tổ hợp lại (ghép kênh) để truyền đi trên một sợi quang. Ở đầu thu, tín hiệu tổ hợp đó được phân giải ra (tách kênh), khôi phục lại tín hiệu gốc rồi đưa vào các đầu cuối khác nhau. Đặc điểm nổi bật của hệ thống ghép kênh theo bước sóng WDM là tận dụng hữu hiệu nguồn tài nguyên băng rộng trong khu vực tổn hao thấp của sợi quang đơn mode, nâng cao rõ rệt dung lượng truyền dẫn của hệ thống đồng thời hạ giá thành của kênh dịch vụ xuống mức thấp nhất. Hiện nay trong viễn thông đều dùng công nghệ ghép kênh theo bước sóng mật độ cao DWDM (Dene Wavelength Devision Multiplexing). Công nghệ DWDM có thể mang đến giải pháp hoàn thiện nhất trong điều kiện công nghệ hiện tại. Một mặt nó vẫn giữ tốc độ xử lý của các linh kiện điện tử ở mức 10Gb/s, đảm bảo thích hợp với sợi quang hiện tại, mặt khác công nghệ DWDM tăng băng thông bằng cách tận dụng cửa sổ làm việc của sợi quang trong khoảng bước sóng 1260 nm đến 1675nm. Khoảng bước sóng 1260 nm đến 1675nm được chia làm nhiều băng sóng hoạt động. Băng O (1260 đến 1360nm), Băng E (1360 đến 1460 nm), Băng S (1460 đến 1530nm), Băng C (1530 đến 1565nm),Băng L (1565 đến 1625nm), Băng U (1625 đến 1675nm). Các kết cấu cơ bản của hệ thống DWDM Hệ thống đơn hướng chỉ truyền theo một chiều trên sợi quang.Để truyền thông tin giữa hai điểm cần hai sợi quang. Hệ thống WDM song hướng truyền hai chiều trên một sợi quang nên chỉ cần 1 sợi quang để có thể trao đổi thông tin giữa 2 điểm Nguyên lý hoạt động của hệ thống DWDM Đầu phát: Tín hiệu quang đến được biến đổi thành tín hiệu quang có bước sóng theo chuẩn G962 sau đó được tập hợp thành tín hiệu quang tổng nhờ bộ ghép sóng quang, được khuếch đại và phát lên sợi quang. Sau khi truyền dẫn qua cự ly dài (80 ÷ 100 km), tín hiệu quang cần được khuếch đại chuyển tiếp. Đầu thu: Tín hiệu quang tổng hợp sẽ được khuếch đại, sau đó được tách thành các tín hiệu quang có bước sóng nhất định ra khỏi tín hiệu quang tổng hợp. Kênh tín hiệu quang giám sát: điều khiển và giám sát tình hình truyền dẫn các kênh tín hiệu quang của hệ thống DWDM . Hệ thống quản lý mạng DWDM: quản lý cấu hình, quản lý sự cố, quản lý tính năng, quản lý bảo mật, … 1.2. CHUYỂN MẠCH QUANG TRONG HỆ THỐNG DWDM Khái niệm chuyển mạch quang Chuyển mạch kênh quang Chuyển mạch kênh quang Mạng quảng bá và lựa chọn: Các điểm nút được nối với nhau thông qua sợi quang và bộ phối ghép không nguồn hình sao, mỗi điểm nút được phân bổ bước sóng khác nhau. Tín hiệu phát đi với đặc tính bước sóng của từng điểm nút và được hội tụ lại qua bộ phối ghép, sau khi phân luồng đi tới đầu thu tin ở các điểm nút, dùng máy thu có điều chỉnh ở mỗi điểm nút để lựa chọn thu. Trong đó máy phát ở các điểm nút có tần số cố định; máy thu có thể điều chỉnh được. Mạng bước sóng dò đường: Tín hiệu trên bước sóng nhất định được trực tiếp dò đường đến điểm nút đích, mà không phải là quảng bá đến toàn mạng. Như vậy giảm được tổn thất năng lượng quang của tín hiệu, đồng thời sử dụng một bước sóng nhiều lần tại các bộ phận không trùng lặp của mạng. CHƯƠNG 2: MẠNG ĐỊNH TUYẾN BƯỚC SÓNG TRONG HỆ THỐNG DWDM 2.1. CẤU HÌNH MẠNG ĐỊNH TUYẾN BƯỚC SÓNG 2.2. KIẾN TRÚC MẠNG ĐỊNH TUYẾN BƯỚC SÓNG 2.1. CẤU HÌNH MẠNG ĐỊNH TUYẾN BƯỚC SÓNG Mạng định tuyến bước sóng là mạng cung cấp các đường quang (lightpaths) tới người sử dụng là các đầu cuối SDH (SONET) hay các router IP. Lightpath là kết nối quang từ kết cuối tới kết cuối (end to end), kết nối quang này vận chuyển tín hiệu quang từ nút nguồn (Source node) tới nút đích (Destination node) qua một bước sóng trên tuyến. OXC 2.2. KIẾN TRÚC MẠNG ĐỊNH TUYẾN BƯỚC SÓNG Khái niệm Mô hình kiến trúc vật lý (Physical Topology) Mô hình kiến trúc đường quang (Lightpath Topology) Khái niệm Topology có nghĩa là hình thù mạng. Bất kỳ mạng thông tin nào cũng có 2 loại kết cấu topology, đó là Physical topology (kiến trúc vật lý) và Logic topology (kiến trúc logic). Trong đó, Physical topology mô tả kết cấu vật lý của nút mạng; Logic topology mô tả sự phân bố dịch vụ của hai nút mạng. Mô hình kiến trúc vật lý (Physical Topology) Kiến trúc vật lý của mạng là một tập các nút đầu cuối, nút định tuyến và các liên kết sợi quang kết nối các nút với nhau về mặt vật lý mà trên đó, người ta có thể thiết lập đường quang giữa các nút đầu cuối. Ðường quang là một đường dẫn đi qua mạng đã có cấp phát bước sóng giữa các nút đầu cuối, và được thiết lập bằng cách cấu hình các nút định tuyến trong mạng. Kiến trúc vật lý có liên quan trực tiếp với việc định tuyến khi đặt đường cáp quang, mục đích thiết kế kiến vật lý là nhằm đáp ứng nhu cầu dịch vụ mạng, do đó quá trình thiết kế được thực hiện sao cho phân bố địa lý của điểm nút mạng và quan hệ kết nối vật lý giữa các điểm nút là tối ưu. Mô hình kiến trúc đường quang (Lightpath Topology) Kiến trúc đường quang (Lightpath Topology) là sự phân bố dịch vụ giữa các điểm nút của mạng. Nó là kiến trúc của các đường quang được cung cấp bởi lớp quang thông qua kiến trúc vật lý. Kiến trúc đường quang (Lightpath topology) thường được gọi là kiến trúc logic (Logical Topology) hay kiến trúc ảo (Virtual Topology). Có thể thay đổi kiến trúc đường quang từ chương trình phần mềm nên có thể xem kiến trúc đường quang là kiến trúc mềm. Mục đích thiết kế kiến trúc đường quang là dựa vào kiến trúc vật lý đã có để nâng cao chỉ tiêu vận hành và kinh doanh mạng tối ưu hóa chức năng mạng của lớp kênh quang. CHƯƠNG 3: CÁC PHƯƠNG PHÁP ĐỊNH TUYẾN BƯỚC SÓNG 3.1. KHÁI NIỆM VỀ ĐỊNH TUYẾN 3.2. PHƯƠNG PHÁP ĐỊNH TUYẾN TĨNH 3.3. PHƯƠNG PHÁP ĐỊNH TUYẾN ĐỘNG 3.1. KHÁI NIỆM VỀ ĐỊNH TUYẾN Khái niệm Định tuyến và gán bước sóng Ví dụ về định tuyến và gán bước sóng với mạng vòng Khái niệm Định tuyến là vấn đề tìm đường đi giữa hai node bất kỳ trong mạng để cung cấp dịch vụ cho người sử dụng. Định tuyến bước sóng là tìm đường đi cho bước sóng quang từ một nút tới một nút bất kỳ trong mạng. Định tuyến và gán bước sóng Trong mạng quang, tìm đường đựơc hiểu theo hai khía cạnh, đó là tìm đường đi vật lý mang được mẫu lưu lượng yêu cầu (Routing) và đưa ra bước sóng phù hợp trên mỗi tuyến (Wavelength Assignment) trong số các bước sóng cho phép. Vấn đề tìm các tuyến và gán bước sóng cho luồng quang được gọi là bài toán định tuyến và gán bước sóng (RWA- Routing and Wavelength Assignment) Để dễ dàng hơn trong việc giải quyết, bài toán RWA được chia ra hai bài toán nhỏ là định tuyến và gán bước sóng. Ví dụ về định tuyến và gán bước sóng với mạng vòng Các tham số : N: số nút mạng t: Số các kết nối cần thiết giữa một nút mạng tới các nút mạng khác. Q: Số cổng kết nối định tuyến. W: Số bước sóng nhỏ nhất trên một tuyến. H: Số hop lớn nhất trên một tuyến (hop là khoảng giữa 2 nút kế cận). Từ kiến trúc vật lý mạng vòng, ta xây dựng được các kiến trúc đường quang khác nhau là: hình vòng (Ring), hình sao (Star) và hình lưới (Mesh) Ví dụ về định tuyến và gán bước sóng với mạng vòng Trường hợp kiến trúc đường quang hình vòng (ring): Ta có các tham số: Số các kết nối cần thiết giữa một nút tới các nút mạng khác t = 3 Số bước sóng tối thiểu trên tuyến W = 2 Số cổng giao tiếp định tuyến trên mỗi nút Q = 4 Số hop tối đa H = 1 Ví dụ về định tuyến và gán bước sóng với mạng vòng Trường hợp kiến trúc đường quang hình sao (Star): Từ OADM hub sẽ định tuyến các lightpath về các OADM1, OADM2, OADM3 và OADM4. Ta có các tham số: Số các kết nối cần thiết giữa một nút tới các nút mạng khác t = 1 Số bước sóng tối thiểu trên tuyến W = 2 Số cổng giao tiếp định tuyến trên mỗi nút Q = 2 Số hop tối đa H = 3 Ví dụ về định tuyến và gán bước sóng với mạng vòng Trường hợp kiến trúc đường quang hình sao (Star): Routing 1 Ta có các tham số: Số các kết nối cần thiết giữa một nút tới các nút mạng khác t = 2 Số bước sóng tối thiểu trên tuyến W = 3 Số cổng giao tiếp định tuyến trên mỗi nút Q = 3 Số hop tối đa H = 2 3.2. PHƯƠNG PHÁP ĐỊNH TUYẾN TĨNH Hệ thống định tuyến tĩnh là hệ thống mà sự định tuyến luôn giữ cố định, độc lập với trạng thái hiện thời của mạng cũng như các lưu lượng người dùng. Định tuyến tĩnh được dựa trên sự dự đoán hơn là dựa vào các hoạt động thực tế của người dùng và mạng. Định tuyến tĩnh là một phần không thể thiếu trong quá trình thiết kế mạng. Tuy nhiên, quá trình định tuyến lại xảy ra không thường xuyên. Bài toán RWA cho lưu lượng tĩnh gọi là bài toán thiết lập luồng quang tĩnh (SLE – Static Lightpath Establishment). 3.2. PHƯƠNG PHÁP ĐỊNH TUYẾN ĐỘNG Định tuyến động tự động cập nhật định tuyến bằng cách áp dụng ngay nhận thức về sự thay đổi trạng thái của người dùng và của mạng. Sự thay đổi không chỉ là trạng thái của các liên kết mà còn là sự dao động giữa lưu lượng người dùng và mạng. Tuy nhiên định tuyến động lại đòi hỏi bộ nhớ và tài nguyên tính toán trong mạng cho việc thu thập các thông tin thời gian thực và đưa ra các quyết định điều khiển. Trong trường hợp lưu lượng động, một luồng quang được thiết lập cho mỗi yêu cầu kết nối đến và luồng quang được giải phóng sau khi một thời gian hạn định. Đối tượng trong trường hợp lưu lượng động là để thiết lập luồng quang và gán bước sóng theo cách tối thiểu tổng số kết nối tắc nghẽn hoặc tối đa số các kết nối được thiết lập trong mạng tại bất cứ thời điểm nào. Bài toán này gọi là bài toán thiết lập luồng quang động (DLE- Dynamic Lightpath Establishment). CHƯƠNG 4: CÁC GIẢI THUẬT ĐỊNH TUYẾN BƯỚC SÓNG Giải thuật định tuyến Giải thuật gán bước sóng Giải thuật định tuyến Bài toán tổng quát Giải thuật Ford Bellman Giải thuật Dijkstra Ta coi mạng định tuyến bước sóng là đồ thị có hướng G = [V,E] với V là tập các đỉnh của đồ thị tương ứng với các nút mạng, E là tập các cạnh của đồ thị tương ứng với số hop trong mạng. Bài toán định tuyến là chúng ta đi tìm đường đi ngắn nhất giữa hai nút trong mạng. Bài toán tìm đường đi ngắn nhất trên đồ thị có hướng dưới dạng tổng quát được phát biểu dưới dạng sau: Cho đồ thị có trọng số G = [V,E], tìm đường đi ngắn nhất từ một đỉnh xuất phát S thuộc V đến đỉnh đích F thuộc V. Độ dài của đường đi này ta sẽ ký hiệu là d[S,F] và gọi là khoảng cách từ S tới F. Nếu như không tồn tại đường đi từ S tới F thì ta đặt khoảng cách đó = + ∞ Bài toán tổng quát Giải thuật Ford Bellman Nội dung: Với đỉnh xuất phát S, gọi d[v] là khoảng cách từ S tới v. Ban đầu d[S] được khởi gán bằng 0 còn các d[v] với v ≠ S được khởi gán bằng +∞. Sau đó ta tối ưu hóa các d[v] như sau: Xét mọi cặp đỉnh u,v của đồ thị, nếu có một cặp đỉnh u,v mà d[v] > d[u]+ c[u,v] thì ta đặt lại d[v]: = d[u] + c[u,v]. Tức là nếu độ dài đường đi từ S tới v lại lớn hơn tổng độ dài đường đi từ S tới u cộng với chi phí đi từ u tới v thì ta sẽ hủy bỏ đường đi từ S tới v đang có và coi đường đi từ S tới v chính là đường đi từ S tới u sau đó đi tiếp từ u tới v. Chú ý rằng ta đặt c[u,v] = +∞ nếu (u,v) không là cung. Thuật toán sẽ kết thúc khi không thể tối ưu thêm bất kỳ nhãn d[v] nào nữa. Các thông số đầu vào (Inputs): là đồ thị G=(V, E) với n đỉnh có ma trận trọng số C; S, F thuộc V. Thông số đầu ra (Output): d[F] là khoảng cách nhỏ nhất từ S đến F. Phạm vi ứng dụng của giải thuật: Giải thuật có thể ứng dụng với nhiều loại topô mạng như hình vòng, hình lưới, hình sao, … Nó áp dụng được với cả hai loại định tuyến tĩnh và định tuyến động. Giải thuật Dijkstra Nội dung: Trong trường hợp đồ thị có trọng số trên các cung không âm, thuật toán do Dijkstra đề xuất được thực hiện trên cơ sở gán nhãn tạm thời cho các đỉnh. Nhãn của mỗi đỉnh cho biết cận trên của độ dài đường đi ngắn nhất tới đỉnh đó. Các nhãn này sẽ được biến đổi (tính lại) nhờ một thủ tục lặp, mà ở mỗi bước lặp một số đỉnh sẽ có nhãn không thay đổi, nhãn đó chính là độ dài đường đi ngắn nhất từ S đến đỉnh đó: Với đỉnh v thuộc V, gọi nhãn d[v] là độ dài đường đi ngắn nhất từ S tới v. Ta sẽ tính các d[v]. Ban đầu d[S] = 0 và d[v] = +∞ với v ≠ S. Nhãn của mỗi đỉnh có hai dạng tự do hay cố định, nhãn tự do có nghĩa là có thể tối ưu hơn được nữa và nhãn cố định tức là d[v] đã băng độ dài đường đi ngắn nhất từ S tới v nên không thể tối ưu thêm. Các thông số đầu vào (Inputs): là đồ thị G=(V, E) với n đỉnh có ma trận trọng số C; S, F thuộc V. Thông số đầu ra (Output): d[F] là khoảng cách nhỏ nhất từ S đến F. Phạm vi ứng dụng của giải thuật: Giải thuật có thể ứng dụng với nhiều loại topô mạng như hình vòng, hình lưới, hình sao, … Nó áp dụng được với cả hai loại định tuyến tĩnh và định tuyến động. Giải thuật gán bước sóng Giải thuật tô màu trong mạng định tuyến theo bước sóng không có khả năng chuyển đổi bước sóng Giải thuật Random Giải thuật tô màu trong mạng định tuyến theo bước sóng không có khả năng chuyển đổi bước sóng Nội dung: Xây dựng một đồ thị G(V,E), trong đó mỗi lightpath trong hệ thống thể hiện bằng một đỉnh trong đồ thị G và tồn tại một cạnh vô hướng giữa hai đỉnh trong đồ thị G nếu các lightpath tương ứng cùng đi qua một liên kết sợi quang vật lý. Tô màu cho các đỉnh của đồ thị G sao cho không có hai đỉnh kế cận nào có màu giống nhau và số màu sử dụng là ít nhất. Các thông số đầu vào (Inputs): Các Lightpath và bước sóng sử dụng trên mạng. Thông số đầu ra (Output): Màu (bước sóng) tương ứng với đỉnh của đồ thị. Phạm vi ứng dụng của giải thuật: Giải thuật có thể ứng dụng với nhiều loại topô mạng như hình vòng, hình lưới, hình sao, … Nó áp dụng được với dạng định tuyến tĩnh. Giải thuật tô màu trong mạng định tuyến theo bước sóng không có khả năng chuyển đổi bước sóng Minh họa cách chuyển từ một bài toán gán bước sóng thành một bài toán tô màu đồ thị: Giả sử có 5 lightpath cần thiết lập là (0,5), (0,2), (1,3), (4,3), và (4,5). Lightpath (0,5) và (0, 2) cùng đi qua liên kết vật lý (0,1) vì thế có một cạnh nối 2 đỉnh (0,5) và (0,2). Tương tự, chúng ta xây dựng được đồ thị như sau: Giải thuật Random Nội dung: Đây là giải thuật gán bước sóng đơn giản nhất, theo đó, nút nguồn sẽ tìm kiếm tất cả các bước sóng để xác định tập bước sóng rỗi trên đường đi đã được xác định. Sau đó, một bước sóng sẽ được chọn ngẫu nhiên (với xác suất như nhau) để gán bước sóng cho lightpath đó. Trong trường hợp thiếu thông tin về tình trạng bước sóng trong mạng thì phương pháp này sẽ dẫn đến kết quả cân bằng được số lượng các bước sóng được sử dụng. Các thông số đầu vào (Inputs): Các Lightpath và bước sóng sử dụng trên mạng. Thông số đầu ra (Output): Bước sóng tương ứng với Lightpath cần gán. Phạm vi ứng dụng của giải thuật: Giải thuật có thể ứng dụng với nhiều loại topô mạng như hình vòng, hình lưới, hình sao, … Nó áp dụng được với dạng định tuyến động.