Đồ án Kỹ thuật định tuyến và mô phỏng

Chương 6 : Chương trình tính toán và mô phỏng định tuyến 58 Chương 6 Chương trình tính toán và mô phỏng định tuyến 6.1 Giới thiệu ngôn ngữ thiết kế : o Lựa chọn ngôn ngữ : Ngôn ngữ sử dụng là ngôn ngữ Delphi, thực hiện trên phần mềm biên dịch 6.0. o Thiết kế giao diện : Bằng cách áp dụng kỹ thuật lập trình đồ hoạ đã tạo ra một chương trình có giao diện đồ hoạ dễ sử dụng, thuận tiện cho các thao tác người dùng, mềm dẻo khi thay đổi cấu hình và tham số mạng. o Thiết kế thuật toán định tuyến : Tiến trình định tuyến sử dụng giải thuật Dijkstra để tính toán đường đi ngắn nhất kết hợp với giao thức OSPF thể hiện các bước mà mỗi Node phải thực hiện trước khi truyền dữ liệu. Bên cạnh đó giá của các liên kết, xác xuất mất gói được tính toán dựa trên một số công thức, lý thuyết toán hàng đợi được đề cập ở những trang tiếp theo. o Các kỹ thuật sử dụng trong quy trình thiết kế : • Để thực hiện “động”, người thực hiện chọn giải pháp sinh các Node động trong thời gian thực. Điều này yêu cầu phải xây dựng một Component có khả năng tạo ra một đối tượng ảnh (Image) trong khi thực hiện. • Việc định tuyến theo giải thuật Dijkstra được thực hiện nhờ việc tối ưu hoá thuật toán “vét cạn” trên cơ sở các mảng động quản lý các Node, các liên kết và giá (nếu có) giữa chúng. Việc định giá ở đây trên cơ sở mức giá chung thấp nhất. Chương 6 : Chương trình tính toán và mô phỏng định tuyến 59 • Việc hình thành bộ đo - ‘giá’ dựa trên cơ sở giải quyết bài toán độ trễ bằng lý thuyết xác suất áp dụng vào các quá trình Poisson, chuỗi cân bằng Markov. • Việc mô phỏng các gói trên mạng được thực hiện nhờ kỹ thuật hoạt hình (Animate) : Đó là giải pháp “chụp ảnh” toàn màn hình, tính toán và vẽ trong bộ nhớ sau đó hiễn thị lại lên màn hình - Đây chính là kỹ thuật màn hình ẩn (Off screen) cao cấp của Delphi. 6.2 Bài toán đặt ra : Cho một tập hợp Node gồm các nước Đông Á, để thực hiện việc quản lý, giả thiết chia khu vực thành hai hệ thống tự trị AS1 và AS2. Trong đó AS1 bao gồm các quốc gia được nối với hai Node ở phía bắc Hà Nội 1 và Hà Nội 2, AS2 là tập hợp những nước còn lại nối với hai Node ở phía nam Hồ Chí Minh 1 và Hồ Chí Minh 2. Nhiệm vụ của bài toán là thực hiện việc quản lý các Node, khi có yêu cầu gởi dữ liệu các Node tính toán đường đi ngắn nhất dựa trên giá tổng đường đi. Giá đường đi được tính thông qua bộ tham số độ rộng băng, độ chiếm dụng, độ trễ, tải lưu lượng, độ tin cậy, MTU. 6.3 Quy trình thiết kế : 6.3.1 Thực hiện giải thuật Dijkstra theo nguyên tắc OSPF : Giải thuật Dijkstra được áp dụng trong thuật toán tìm đường đi ngắn nhất qua mạng OSPF. Để thực hiện tiến trình định tuyến cần thực hiện các bước : 1. Khởi tạo một Topo mạng bao gồm : + Các Node nội vùng. + Các Node liên vùng. + Tuyến liên kết giữa các Node. + Bộ giá của từng tuyến. 2. Tìm đường đi ngắn nhất giữa các Node : Việc định tuyến phải đáp ứng được hai yêu cầu : Chương 6 : Chương trình tính toán và mô phỏng định tuyến 60 + Định tuyến ngầm định : Đường đi ngầm định được đánh giá theo các giá trị của bộ đo. Định tuyến mặc định chỉ ra đường đi ngắn nhất từ node nguồn đến node đích khi có yêu cầu kết nối. Việc chỉ ra đường đi ngắn nhất dựa trên giải thuật Dijkstra trên cơ sở đánh giá các bộ tham số được lưu trữ tại cơ sở dữ liệu của mỗi node. Đường đi ngắn nhất ở đây chưa xét đến các yêu cầu của node nguồn, nó có thể khác với đường đi được chỉ ra trong định tuyến tự động. + Định tuyến tự động : Đường đi ngắn nhất được tính toán khi Node nguồn có yêu cầu đáp ứng về lưu lượng. Định tuyến tự động chỉ ra đường đi cụ thể qua mạng khi biết được yêu cầu về lưu lượng cũng như thời gian tại node nguồn. Như vậy, khi tìm đường ngắn nhất, chương trình phải thực hiện vòng lặp định tuyến như sau : + Tìm đường đi ngắn nhất ngầm định theo OSPF mặc định. Trên cơ sở đó, thực hiện đánh giá yêu cầu về lưu lượng truyền tải, và thực hiện vòng lặp phân tải như sau : ¾ Đánh giá BW còn lại . ¾ Nếu BW đáp ứng yêu cầu, thực hiện truyền toàn bộ lưu lượng trên tuyến được chỉ ra bởi định tuyến “chìm”. ¾ Nếu BW còn lại nhỏ hơn yêu cầu thì thực hiện phân lưu lượng : ƒ Thực hiện truyền tải trên tuyến một phần lưu lượng phù hợp với BW của tuyến đó; ƒ Phần lưu lượng còn lại : được truyền tải trên tuyến chỉ ra bởi việc thực hiện vòng lặp lại từ đầu. 3. Minh họa bài toán : + Hiển thị đầy đủ được quá trình định tuyến, chọn đường, tìm đường. + Chứng tỏ được giải thuật Dijkstra chạy trên các nguyên tắc của OSPF. Chương 6 : Chương trình tính toán và mô phỏng định tuyến 61 6.3.2 Tính toán thời gian trễ và xác suất mất gói : 6.3.2.1 Giả thiết : Ta có một trường chuyển mạch với cơ chế bộ nhớ được chia sẻ (Shared-Memory) kiểu phân vùng hoàn toàn cho hàng đợi đầu ra với N đường vào (Complete Partioning of Output Queue with N input line). Các bộ đệm lối vào và ra sử dụng chung một bộ nhớ bán dẫn RAM.Các gói có tốc độ đến rất lớn cùng hướng tới hàng đợi với cơ chế FIFO (first in , first out). Vấn đề đặt ra là làm như thế nào để có thể tính toán được thời gian trễ, xác suất mất gói theo các thông số đầu vào và của hàng đợi ? 6.3.2.2 Phân tích : Giả sử có N đầu vào được đưa đến N bộ đệm có kích thước b gói. Trạng thái bộ đệm ra sẽ tuỳ thuộc vào số lượng các gói có cùng một địa chỉ cổng. Sơ đồ chia sẽ bộ nhớ : Các đại lượng đầu vào : ¾ Chiều dài hàng đợi : b gói . ¾ Số đường vào : N. ¾ Hệ số tải được phép : p , p = [0,1]. Do đó : -Xác suất một gói đến bộ đệm ra là p / N. -Xác suất một giá trị A gói bất kỳ đến và chuyển qua bộ đệm ra sẽ tuân theo phân bố nhị thức BD (Binary Distributtion) là : Hàng đợi ngõ ra 1 2 . . . . . . . . . . . . . N-1 N b gói b gói Chương 6 : Chương trình tính toán và mô phỏng định tuyến 62 ak = P(A=k) = kNk N p N p K N −⎟⎠ ⎞⎜⎝ ⎛ −⎟⎠ ⎞⎜⎝ ⎛⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ 1 víi k = 0,1,.. N. (6.1) Với số lượng đầu vào rất lớn N → ∞ thì quá trình đến được biểu diễn như một quá trình Poisson. ak = P(A=k) = !k ep p k − víi k = 0,1,.. N. (6.2) Gọi Q là số gói đến bộ đệm vào cuối khe thời gian thứ m. Nếu có (Q+1) gói ở trong bộ đệm thì ngay lập tức một gói sẽ được chuyển trong khe thứ m mà không có thời gian trễ, còn Q gói sẽ ở lại trong bộ đệm cho đến khi có gói đến trong khe thời gian tiếp theo. Khi N → ∞ vµ b → ∞ bộ đệm với cỡ Q giống như kiểu M/D/1. Còn với một giới hạn N và b thì Q xác định bởi trạng thái giới hạn, ngắt quãng theo thời gian của chuỗi Markov. Xác suất chuyển giữa hai trạng thái j, i là : Pij = P(Q = j / Q = i) Pij = ∑ += N ik ka 1 víi ak ®−îc tÝnh theo c«ng thøc (6.1) và (6.2) Gọi qn là xác suất trạng thái bền vững của Q gói ở bộ đệm thì theo phương trình cân bằng của chuỗi Markov ta viết được : ∑ = −++ += b i ninn qapaq 0 1110 với 0 < n ≤ b (6.3) q1 = (1- a0 - a1)/a0 (6.4) ⇒ q0 = ∑ = + b n o n a q 0 1( 1 (6.5) Chương 6 : Chương trình tính toán và mô phỏng định tuyến 63 Sẽ không có gói tin nào trong bộ đệm tại thời điểm m nếu như Q⏐m-1= 0 vµ Am = 0. Có nghiã là : nếu đặt ρ0 là lưu lượng chuẩn hoá được đưa vào chuyển mạch, cũng chính là hệ số của đầu ra thì khả năng chuyển qua là : ρ0 = 1 - q0a0 , víi q0 ®−îc suy ra tõ (6.3) (6.4) vµ (6.5) ⇒ X¸c suÊt gãi chuyÓn qua lµ ρ0 / p ⇒ X¸c suÊt mÊt gãi : P (packet lost) = 1 - ( ρ 0 / p ) (6.6) Với kiểu chuyển mạch dùng chung bộ nhớ này thì trễ qua chuyển mạch chỉ xảy ra khi hai hay nhiều packet từ các đầu vào khác nhau hướng đến cùng một đầu ra. Thời gian đợi trung bình của một Packet khi qua bộ đệm kiểu FIFO là : ∑ = −== b n n aq q nQW 1 000 1ρ (6.7) Khi N = ∞ vµ b = ∞ ta được thời gian trễ trung bình giống như một hàng đợi M/D/1 : )1(2 p pW −= Như vậy với cỡ b (gói ) của bộ đệm, hệ số p cùng với số đường vào N ta tính được : - X¸c suÊt mÊt gãi P = 1 - ( ρ0 / p ) theo (6.6). - Thời gian trễ qua chuyển mạch theo (6.7). Các kết quả tính toán cho thấy rằng, với N ≥ 32 thì xác suất mất gói là như nhau với cùng một cỡ b của bộ đệm và hệ số tải cho phép p. Điều này có thể giải thích theo (6.1) với N rất lớn thì khi tăng k, xác suất trạng thái ak = P(A = k) sẽ giảm rất chậm, các xác suất P tìm được theo (6.6) càng thay đổi ít. Vì vậy xác suất mất gói là gần như nhau. Thực tế, khi kiểm tra trên chương trình cho thấy với giá trị N > 20 các thông số tìm được thay đổi rất ít. Chương 6 : Chương trình tính toán và mô phỏng định tuyến 64 6.4 Sơ đồ khối các thủ tục chính trong chương trình : 6.4.1 Sơ đồ khối thủ tục tính Dijkstra : Begin S=ngd[1], t=ngd[2] i :=1 , j=1 d[i]=1000000, tt[i]=s chua[i]=true i <= 21 ? Last=s , d[s]=0 chua[s]= False i= i+1 chua[t] ? End d[i]= d[last]+gia[last,i] tt[i]= last i= dtlc[last,j]+1 Chua[i] and d[i]>=d[last]+gia[last,i]? j <= dslc[last]? j= j+1 Min=1000000, i=1 i= i+1 Chua[i] and min>=d[i]? Min=d[i], last=i Chua[last]= False i <= 21 ? N Y Y Y N Y N N Y N Y N Y vẽ đường đi và lưu kết quả Chương 6 : Chương trình tính toán và mô phỏng định tuyến 65 6.4.2 Sơ đồ khối thủ tục tính độ rộng băng thông : 6.4.3 Sơ đồ khối thủ tục tính giá : Begin n= truoc[a,1] i=2 p < 10 ? End N u1 = truoc[a,i]-1 u2 = truoc[a,i+1]-1 p = Mgia[u1,u2,0] pp= m / p inc(dgia[u1+1,u2+1],pp) p1= dgia[u1+1,u2+1]* p conlai[a,i-1] = p – p1 conlai[a,i-1]= 8 i <= n ? Inc(i) Y m > 0 ? Tinhgia Y N N Chương 6 : Chương trình tính toán và mô phỏng định tuyến 66 6.5 Sử dụng chương trình : 6.5.1 Giao diện thiết lập Topo mạng : Giả thiết ta chia khu vực ra làm hai AS ở ô chọn bên trái và phải. Đầu tiên người sử dụng kích hoạt vào ô “Tạo mới Topo” để thiết lập cấu hình mạng với các Node chọn là các quốc gia ở trong ô chọn. Ngoài ra còn có thêm chức năng “Thêm tuyến” và “Xóa tuyến” giữa hai Node bất kỳ khi ta kích chuột phải vào hai Node sau khi “Tạo mới Topo”. Cuối cùng nhấn nút chọn “Lưu Topo” để nạp cấu hình mạng phục vụ cho việc lưu trữ, xữ lý. Begin i=1 , j=1 End m = dtlc[n,j] p1 = Mgia[n-1,m,0] p2 = dgia[n,m+1] p = p1*p2 b <= 5 ? Inc(b) Y n= i b=2 p = p + Mgia[n-1,m,b] gia[n,m+1] = trunc(p) j <= dslc(n)? Inc(j) i <= 21 ? Inc(i) Y Y N N N Chương 6 : Chương trình tính toán và mô phỏng định tuyến 67 6.5.2 Giao diện nạp băng thông cho từng tuyến : Chương 6 : Chương trình tính toán và mô phỏng định tuyến 68 6.5.3 Giao diện thay đổi giá : 6.5.4 Giao diện chọn Node nguồn và Node đích : Chương 6 : Chương trình tính toán và mô phỏng định tuyến 69 6.5.5 Giao diện mô phỏng quá trình truyền bản tin LSA cho các Node : 6.5.6 Giao diện mô phỏng tiến trình truyền bản tin từ nguồn đến đích : Chương 6 : Chương trình tính toán và mô phỏng định tuyến 70 6.5.7 Giao diện minh hoạ đồ thị xác suất mất gói và thời gian trễ : 6.6 Kết luận chương : Chương trình mô phỏng ở trên mặc dù thể hiện được khá rõ về cách quản trị băng thông, cách tính toán tìm đường ngắn nhất dựa trên giải thuật Dijkstra, cũng như việc minh họa trễ bằng đồ thị. Nhưng về phương diện thực tế vẫn chưa đảm bảo, đặc biệt là vấn đề quản trị động các Node theo thời gian thực. Từ đó tính toán phân tải lưu lượng trên từng Node nhằm mục đích tối ưu định tuyến, sử dụng tối đa băng thông đường truyền tránh tình trạng có những tuyến quá rỗi lại có những tuyến quá bận. Bên cạnh đó chương trình vẫn chưa thể hiện sự tương quan giữa các giải thuật khác nhau bằng cách thực hiện định tuyến trên các giải thuật khác. Trong thời gian tới em sẽ cố gắng hơn để hoàn thiện chương trình này.