Báo cáo Vấn đề Optimizer

Mục Lục I.Tổng quan về chương trình 1. Mục đích của chương trình: Hiện nay vấn đề tiết kiệm năng lượng đang được đặt ra như một vấn đề thiết yếu trong tất cả các lĩnh vực của cuộc sống. Trong việc quản lí và sử dụng Data Center vấn đề này càng cần thiết hơn vì nhiều lúc(nhất là vào ban đêm, giờ thấp điểm) số lượng yêu cầu kết nối rất nhỏ trong khi tất cả các chuyển mạch vẫn hoạt động gây ra sự lãng phí không đáng có. Chính vì thế chúng em thực hiện chương trình này mong muốn có thể tối ưu hóa hệ thống hết mức có thể mà vẫn đáp ứng được nhu cầu của người dùng, qua đó có thể tiết kiệm được công suất sử dụng.Để thực hiện quá trình này thì vấn đề Optimizer là vô cùng cần thiết. 2. Giới thiệu chung về Optimizer và thuật toán sử dụng Optimizer là quá trình tối ưu hóa sơ đồ hệ thống(Topology) từ dạng phức tạp về dạng đơn giản hơn.Để thực hiện được điều đó chúng ta sử dụng thuật toán Greedybin-packing.Đối với thuật toán này chúng ta sẽ chọn đường cho các kết nối theo đường trái nhất giúp cho sơ đồ hệ thống được giảm thiểu 3. Giới thiệu chung về chương trình Chương trình bao gồm 11 khối chức năng chính được mô tả như hình vẽ phía dưới.Chương trình hoạt động theo các bước: Nhập dữ liệu Đọc các yêu cầu từ ma trận kết nối Giải quyết yêu cầu bằng đường đi bên trái nhất. Nếu không giải quyết được yêu cầu(không tìm được đường đi hay các đường đi đã quá tải) thì thêm yêu cầu vào danh sách từ chối In kết quả ra màn hình II. Các khối chức năng cụ thể của chương trình *)Các hàm phục vụ cho quá trình tính toán Hàm tạo ma trận m hàng n cột với tất cả các phần tử bằng 0 def taomt(m,n):# Khai báo hàm a=[]#Khởi tạo ma trận a rỗng i=0#Khai báo biến i j=0#Khai báo biến j for i in range(m):#i chạy từ 0 đến m-1 b=[]#Khai báo b rỗng a.append(b)#Thêm b vào a #Như vậy sau bước này ta có ma trận a có m hàng for i in range(m):#i chạy 0->m-1 for j in range(n):#j chạy 0-> n-1 a[i].append(0)#Thêm 0 vào hàng i để tạo ra cột #Như vậy sau bước này ta có ma trận m hàng n cột tất cả phần tử bằng 0 return a# Trả về a Hàm tính xy def mu(x,y):#Khai báo hàm s=1#Khai báo s if y==0:#Nếu y=0 return 1#Trả về 1 else: for i in range(y):# s=s*x return(s) Hàm add toàn bộ list y vào list x def addlist(x,y): for i in range(len(y)): x.append(y[i]) return x 1.Khối nhập dữ liệu đầu vào l=input("Nhap so server\n") n=input("Nhap so chuyen mach Top Of Rack\n") m=input("Nhap so chuyen mach tich hop\n") h=input("Nhap so chuyen mach loi (core)\n") f=input("Nhap so Top Of Rack toi da ket noi vao mot chuyen mach tich hop\n") e=input("Nhap so server toi da ket noi vao mot Top Of Rack\n") dl=float(raw_input("Nhap capacity cua he thong")) bitmin=float(raw_input("Nhap bitrate toi thieu cua cac ket noi")) bitmax=float(raw_input("Nhap bitrate toi da cua cac ket noi")) mi1=input("Nhap cong suat toi thieu cua tang chuyen mach loi") ma1=input("Nhap cong suat toi da cua tang chuyen mach loi") mi2=input("Nhap cong suat toi thieu cua tang chuyen mach tich hop") ma2=input("Nhap cong suat toi da cua tang chuyen mach tich hop") mi3=input("Nhap cong suat toi thieu cua tang chuyen mach Top Of Rack") ma3=input("Nhap cong suat toi da cua tang chuyen mach Top Of Rack") 2. Khối tạo ma trận bit rate 2.1 Ý nghĩa: Lưu bitrate của các yêu cầu kết nối 2.2 Định dạng ma trận Ma trận gồm 1 hàng và l cột ( l là số server). Mỗi cột đại diện cho 1 server. Server nào phát đi yêu cầu thì giá trị của cột tương ứng trong ma trận sẽ có giá trị là bitrate của yêu cầu phát đi. Server nào không phát đi yêu cầu thì giá trị cột tương ứng trong ma trận sẽ có giá trị 0. Ví dụ: Có 5 server. Server 2,5 không phát yêu cầu. Server 1,3,4 phát yêu cầu với bitrate tương ứng là 0.1;0.3;0.2. ta có ma trận: 0.1 0 0.3 0.2 0 2.3 Giải thuật Ta sẽ tạo ngẫu nhiên các yêu cầu kết nối theo cách: +) Tạo ngẫu nhiên 1 trong 2 số 1 và 0 tương ứng với hai trường hợp phát và không phát yêu cầu +) Nhân số đã tạo ở trên với 1 số ngẫu nhiên trong khoảng min-> max đã cho. Như thế: Khi server phát yêu cầu ta sẽ có giá trị 1*x=x(x nằm trong khoảng min-> max) Khi server không phát yêu cầu ta có giá trị 0*x=0 2.4 Thực hiện def tao_bitrate(l,m1,m2): #Các tham số: #l: Số server #m1: bitrate min của yêu cầu #m2: bitrate max của yêu cầu i=0 a=taomt(1,l)#Tạo ma trận 1 hàng l cột for i in range (l): a[0][i]=random.randint(0,1)*random.uniform(m1,m2) #Lệnh random.randint(0,1) random ra 1 trong 2 số 0 hoặc 1 #Lệnh random.uniform(m1,m2) random ra 1 số bất kì trong khoảng m1,m2 return a 3. Khối tạo ma trận công suất 3.1 Ý nghĩa Lưu công suất trên từng chuyển mạch của hệ thống.Phục vụ cho quá trình tính toán công suất tiết kiêm được của hệ thống 3.2Định dạng ma trận Ma trận gồm 3 hàng, n cột. Trong đó : Hàng 1 thể hiện công suất từng chuyển mạch lõi (core) Hàng 2 thể hiện công suất từng chuyển mạch tích hợp Hàng 3 thể hiện công suất từng chuyển mạch top of rack Vì số core ,chuyển mạch tích hợp,top of rack là không như nhau nên ta tạo ma trận với số cột lớn nhất là n.Do đó với những phần tử dư ra trong từng hàng ta mặc định bằng 0. Ví dụ: Hệ thống có 2 chuyển mạch lõi với công suất 180 và 185 W, 4 chuyển mạch tích hợp với công suất 150,152,151,154 W, 6 chuyển mạch top of rack với công suất 123, 125,122,127,124,128 W. Ta sẽ có ma trận công suất: 180 185 0 0 0 0 150 152 151 154 0 0 123 125 122 127 124 128 3.3 Giải thuật Tạo ma trận (3,n) với tất cả các phần tử bằng 0 Hàng 1 nhập giá trị công suất của core bằng hàm random Hàng 2 nhập giá trị công suất của chuyển mạch tích hợp bằng hàm random Hàng 3 nhập giá trị công suất của top of rack bằng hàm random Với các giá trị công suất min ,max được nhập qua các tham số mi1,ma1,mi2,ma2,mi3,ma3 3.4 Thực hiện #Hàm tạo ma trận công suất def tao_mtcs(h,m,n,mi1,ma1,mi2,ma2,mi3,ma3): # số core : h, số top of rack :m, số top of switch :n #mi1, ma1, mi2, ma2, mi3, ma3 lần lượt là công suất min, max của core, top of rack, top #of switch a=taomt(3,n) #tạo ma trận 3 hàng n cột for i in range(h): a[0][i]=random.randint(mi1,ma1) #tạo hàng công suất của core lấy giá trị random trong đoạn [mi1,ma1] for i in range(m): a[1][i]=random.randint(mi2,ma2) #tạo hàng công suất của core lấy giá trị random trong đoạn [mi2,ma2] for i in range(n): a[2][i]=random.randint(mi3,ma3) #tạo hàng công suất của core lấy giá trị random trong đoạn [mi3,ma3] return a 4. Khối tạo ma trận kết nối 4.1 Ý nghĩa Ma trận kết nối thể hiện thông tin đầy đủ về tất cả các yêu cầu, bao gồm: Server nguồn Server đích Dung lượng yêu cầu 4.2 Định dạng ma trận Ma trận bao gồm l hàng l cột với l là số server. Các hàng tượng trưng cho server phát. Các cột tượng trưng cho server thu.Tại vị trí [i][j] trong ma trận: Nếu giá trị của ma trận khác 0 : tồn tại yêu cầu từ server i đến server j với dung lượng là giá trị của ma trận tại vị trí [i][j] Nếu giá trị của ma trận bằng 0: Không tồn tại yêu cầu từ server i đến server j 4.3 Giải thuật Trước khi chúng ta tạo ma trận kết nối chúng ta đã có ma trận bitrate thể hiện bitrate của các server phát do đó chúng ta phải tạo ma trận kết nối tương ứng với ma trận bitratr e này. Cách thức thực hiện: Khởi tạo ma trận kết nối l hàng l cột tất cả bằng 0 Duyệt ma trận bitrate Nếu có yêu cầu(giá trị ma trận bitrate khác 0) tại vị trí i Random một số bất kì j (khác i) làm server thu Gán giá trị của ma trận kết nối tại vị trí [i][j] là giá trị bitrate tương ứng 4.4 Thực hiện def tao_mtketnoi(bit,l): #Đầu vào: #bit: ma trận bitrate #l: số server k=0#k : số bất kì làm server đích kq=taomt(l,l)#Khởi tạo ma trận l hàng l cột for i in range(l): if bit[0][i]!=0:#Nếu tồn tại yêu cầu k=i#Đầu tiên gán k=i while(k==i):#Kiểm tra k có bằng i hay ko k=random.randint(0,l-1)#Nếu có random ra 1 số bất kì từ 0=>l-1.Sau đó quay lên kiểm tra xem k có khác i hay ko. Nếu vẫn khác thì lặp lại đến khi k khác i kq[i][k]=bit[0][i]#Gán giá trị return kq 5. Khối tạo 3 ma trận thể hiện kết nối 5.1 Ý nghĩa Ta nhận thấy rằng trong topology biểu diễn hệ thống không phải 2 chuyển mạch bất kì nào cũng nối với nhau, do đó chúng ta cần có những ma trận thể hiện sự kết nối giữa các tầng chuyển với nhau để khi tiến hành Optimizer chúng ta biết được những chuyển mạch nào có thể nối được với nhau và những chuyển mạch nào không nối với nhau. 5.2 Định dạng ma trận Trong Topology hệ thống chúng ta thấy rõ hệ thống bao gồm các tầng theo thứ tự từ trên xuống: Chuyển mạch lõi Chuyển mạch tích hợp Chuyển mạch top of rack Server Do đó chúng ta phải thể hiện các kết nối : Chuyển mạch lõi-chuyển mạch tích hơp Chuyển mạch tích hợp-chuyển mạch top of rack Chuyển mạch top of rack-Server Do đó chúng ta sẽ xây dựng 3 ma trận thể hiện cho 3 kết nối phải thể hiện. Mỗi tầng có định dạng như sau: Ma trận thể hiện kêt nối giữa tầng i và tầng j . Trong đó tầng i nằm phía trên tầng j. Tầng i có a chuyển mạch, mỗi chuyển mạch ở tầng i nối với b chuyển mạch ở tầng j.Ta sẽ có ma trận a hàng b+1 cột trong đó: Cột đầu tiên của mỗi hàng biểu diễn số thứ tự của chuyển mạch ở tầng i Các cột từ thứ 2 đến hết của mỗi hàng thể hiện số thứ tự của chuyển mạch ở tầng j có kết nối với i. Ví dụ: Ta có sơ đồ kết nối giữa 2 tầng như sau: Ta thấy tâng i ( phía trên) có 3 chuyển mạch. Tầng j ( phía dưới) có 6 chuyển mạch.Mỗi chuyển mạch ở tầng i có 4 chuyển mạch ở tầng j nối vào nó. Chuyển mạch thứ 1,2,3, 4 của tầng j nối với chuyển mạch 1 của tầng i. Chuyển mạch 1,2,3,4 của tầng j nối với chuyển mạch 2 của tầng i. Chuyển mạch 3,4,5,6 của tầng j nối với chuyển mạch 3 của tầng i.Từ đó ta có ma trận : 1 1 2 3 4 2 1 2 3 4 3 3 4 5 6 5.3 Giải thuật và thực hiện 5.3.1 Ma trận thể hiện kết nối giữa tầng chuyển mạch lõi-chuyển mạch tích hợp a ) Giải thuật Ở lớp kết nối này mỗi chuyển mạch lõi đều nối với tất cả các chuyển mạch tích hơp. Ví dụ: ta có 2 chuyển mạch lõi và 4 chuyển mạch tích hợp ta sẽ có sơ đồ kết nối: Do đó ta có giải thuật: b) Thực hiện def tao_core(m,h): #Đầu vào: #m: số chuyển mạch tích hợp #h: số chuyển mạch lõi i=0 j=0 a=taomt(h,m+1)#Tạo ma trận h hàng m+1 cột for i in range(h): a[i][0]=i+1#Gán cột đầu tiên mỗi hàng là số thứ tự của chuyển mạch tầng core for i in range(h): for j in range(1,m+1,1): a[i][j]=j#Gán các cột còn lại là các chuyển mạch tích hợp nối đến core return a 5.3.2 Ma trận thể hiện kết nối giữa tầng chuyển mạch tích hợp-chuyển mạch top of rack a. Giải thuật Ở tầng này mỗi chuyển mạch ở tầng i(tầng tích hợp) nối với f chuyển mạch ở tầng j(tầng top of rack).f được nhập từ bàn phím.Ta thực hiện như sau: Tạo 1 ma trận m hàng f+1 cột Gán cột đầu tiên của mỗi hàng là số thứ tự của chuyển mạch ở tầng chuyển mạch tích hợp Gán các cột còn lại là số thứ tự của chuyển mạch ở tầng top of rack nối với chuyển mạch ở tầng tích hợp nằm ở cột đầu tiên của hàng đó.Ta sẽ thực hiện gán như sau: Tính d=n/m(n: số chuyển mạch top of rack, m: số chuyển mạch tích hợp) Ta thấy trên hình chuyển mạch tích hợp thứ 1,2....3 sẽ được gán với f(f=3) chuyển mạch ở tầng dưới bắt đầu từ chuyển mạch 1,3,5 .Nếu đặt x là số thứ tự chuyển mạch ở tầng trên ( tầng i) thì ta có vị trí đầu tiên được gán của một chuyển mạch ở tầng i là:(x-1)*d+1 Chuyển mạch thứ 4(chuyển mạch cuối) sẽ được gán với f chuyển mạch bắt đầu từ vị trí cuối cùng đếm ngược lại b. Thực hiện def tao_tichhop(n,m,f): #Đầu vào: #n: số chuyển mạch top of rack #m: số chuyển mạch tích hợp #f: Số chuyển mạch top of rack nối với 1 chuyển mạch tích hợp i=0 j=0 d=n/m#Tính d a=taomt(m,f+1)#Tạo ma trận m hàng f+1 cột for i in range(m): a[i][0]=i+1#Gán hàng đầu tiên là số thứ tự của chuyển mạch ở tầng tích hợp for i in range(m-1):#Với các chuyển mạch ở vị trí 1...m-1 for j in range(1,f+1,1):#Mỗi chuyển mạch được gán với f chuyển mạch ở tầng dưới a[i][j]=i*d+j#Gán các chuyển mạch bắt đầu từ vị trí i*d+1 đến i*d+f cho chuyển mạch thứ i if (a[i][j]>n):#Nếu số chuyển mạch được gán vượt quá n a[i][j]=i*d+1-(i*d+j-n)#Sẽ gán theo chiểu ngược lại bắt đầu từ i*d -> i*d-1 -> i*d-2... for i in range(1,f+1,1):#Chuyển mạch cuối cùng a[m-1][i]=n-i+1#Gán ngược bắt đầu từ chuyển mạch cuối return a 5.3.3Ma trận thể hiện kết nối giữa tầng chuyển mạch top of rack và các Server a. Giải thuật Ở tầng này mỗi chuyển mạch ở tầng i(tầng top of rack) nối với e server.e được nhập từ bàn phím.Ta thực hiện như sau: Tạo 1 ma trận n hàng e+1 cột Gán cột đầu tiên của mỗi hàng là số thứ tự của chuyển mạch ở tầng chuyển mạch top of rack Gán các cột còn lại là số thứ tự của server nối với chuyển mạch ở tầng top of rack nằm ở cột đầu tiên của hàng đó.Ta sẽ thực hiện gán như sau: Tính d=l/n(l: số server, n: số chuyển mạch top of rack) Ta thấy trên hình chuyển mạch tích hợp thứ 1,2 sẽ được gán với e(e=4) chuyển mạch ở tầng dưới bắt đầu từ chuyển mạch 1,3 .Nếu đặt x là số thứ tự chuyển mạch ở tầng trên ( tầng i) thì ta có vị trí đầu tiên được gán của một chuyển mạch ở tầng i là:(x-1)*d+1 Chuyển mạch thứ 4(chuyển mạch cuối) sẽ được gán với e chuyển mạch bắt đầu từ vị trí cuối cùng đếm ngược lại b. Thực hiện def tao_topofrack(l,n,e): #Đầu vào : #l:số server #n:số chuyển mạch top of rack #e: số server nối với 1 top of rack i=0 j=0 d=l/n#Tính d a=taomt(n,e+1)#Tạo ma trận n hàng e+1 cột for i in range(n): a[i][0]=i+1#Gán cột đầu tiên là số thứ tự của chuyển mạch top of rack for i in range(n-1): #Với các chuyển mạch ở vị trí 1...n-1 for j in range(1,e+1,1): ):#Mỗi chuyển mạch được gán với e server a[i][j]=i*d+j #Gán các server bắt đầu từ vị trí i*d+1 đến i*d+e cho chuyển mạch thứ i if (a[i][j]>l): #Nếu số chuyển mạch được gán vượt quá n a[i][j]=i*d+1-(i*d+j-l) )#Sẽ gán theo chiểu ngược lại bắt đầu từ i*d -> i*d-1 -> i*d-2... for i in range(1,e+1,1):#Đối với chuyển mạch cuối a[n-1][i]=l-i+1 #Gán ngược bắt đầu từ chuyển mạch cuối return a 6. Khối tìm đường cho kết nối 6.1 Ý nghĩa Để thực hiện Optimizer một kết nối bất kì từ server a đến server b ta phải thực hiện tìm tất cả các đường đi có thể cho kết nối đó trước khi quyết định chọn đường đi nào cho kết nối. 6.2 Định dạng ma trận chứa đường đi Giả sử ta có một Topology như hình vẽ. Hệ thống có 2 chuyển mạch lõi, 4 chuyển mạch tích hợp , 4 chuyển mạch top of rack, 8 server. Để thuận tiện trong quá trình tìm đường ta ngầm định đánh số các chuyển mạch theo thứ tự từ trái sang phải bắt đầu từ 1. Giả sử ta phải tìm đường đi từ server số 1 đến server số 3 ta có thể chọn đường đi như sau: 1 -> 1 -> 1 -> 1 -> 2 -> 2 -> 3 Từ đó ta thấy mỗi đường đi từ server a đến server b bất kì sẽ phải trải qua 7 chặng. Do đó để biểu diễn đường đi ta sẽ sử dụng một ma trận bao gồm 7 phần tử tương ứng với 7 chặng của đường đi. Để lưu tất cả các đường đi ta sẽ sử dụng một ma trận bao gồm x phần tử ( với x là số đường đi có thể tìm được cho kết nối đã cho). Mỗi phần tử của ma trận này là một ma trận bao gồm 7 phần tử tương ứng với 7 chặng của đường đi. 6.3 Giải thuật Như ở phần 5 ta thấy là để thể hiện kết nối giữa 2 tầng(tầng i,tầng j) của hệ thống ta sử dụng ma trận như sau: Số thứ tự chuyển mạch ở tầng j nối với chuyển mạch ở tầng i tương ứng Số thứ tự chuyển mạch ở tầng i ii Dựa trên các ma trận thể hiện kết nối này chúng ta sẽ thực hiện việc tìm đường bằng cách tìm tất cả các đường đi từ server phát đến tất cả các server khác sau đó lọc ra những đường đi đến server đích. Vụ thể như sau: Gán server phát vào ma trận đường đi Duyệt ma trận thể hiện kết nối tầng top of rack-server xem chuyển mạch top of rack nào nối với server đường đi. Khi tìm được gán chuyển mạch này vào ma trận đường đi Duyệt các đường đi thu được sau bước 2 lấy ra các chuyển mạch top of rack trong các đường đi này. Sau đó duyệt ma trận kết nối tầng tích hợp-top of rack tìm các chuyển mạch tích hợp có kết nối đến chuyển mạch top of rack đã lấy ra ở trên. Khi tìm thấy gán chuyển mạch vào ma trận đường đi Làm tương tự với các tầng tiếp theo ta sẽ thu được một ma trận đường bao gồm các đường đi từ server a đến server b nào đó Lọc ra trong ma trận trên những đường đi có điểm đích là server đã cho 6.4 Thực hiện def timduong(x,y,l,n,m,h,e,f,a,b,c): # Đầu vào #x: server nguồn #y: server đích #l: số server #n: số chuyển mạch top of rack #m: số chuyển mạch tích hợp #h: số chuyển mạch lõi #e: số server nối vào 1 chuyển mạch top of rack #f: số chuyển mạch top of rack nối vào 1 chuyển mạch tích hợp #a: Ma trận thể hiện kết nối tầng core-tích hợp #b: Ma trận thể hiện kết nối tầng tích hợp-top of rack #c: Ma trận thể hiện kết nối tầng top of rack –server mtd=[]#Khởi tạo ma trận chứa đường kq=[]#Khởi tạo ma trận kết quả trả về i=0 j=0 k=0 t1=[]#Biến tạm thời chứa tập hợp các đường đi t2=[]#Biến tạm thời lưu 1 đường đi cụ thể for i in range(n): for j in range(1,e+1,1):#Duyệt ma trận kết nối top of rack-server if (c[i][j]==x):#Tìm ra những top of rack có nối đến server x t2.append(x)#Thêm x vào t2 t2.append(c[i][0])#Thêm top of rack tìm được vào t2 t1.append(t2)#Thêm t2 vào tập hợp đường t2=[]#Xóa t2 để phục vụ cho lần tìm tiếp theo mtd=t1#Sau khi duyêth xong gán t1 cho ma trận đường t1=[]#Xóa t1 để phục vụ cho việc duyệt tầng tiếp theo for i in range( len(mtd)):#Duyệt ma trận đường for j in range(m): for k in range(1,f+1,1):#Duyệt ma trận kết nối tầng tích hợp-top of rack if b[j][k]==mtd[i][1]:#Xét những top of rack có trong ma trận đường. #Tìm các chuyển mạch tích hợp nối vào top of rack đó addlist(t2,mtd[i])#Sau khi tìm được ta sẽ copy đường đi đã có t2.append(b[j][0]) #Thêm vào đó các chuyển mạch tích hợp mới tìm được t1.append(t2) #Thêm t2 vào tập hợp đường t1 t2=[]#Xóa t2 để phục vụ cho lần tìm tiếp theo mtd=[]#Xóa ma trận đường addlist(mtd,t1)#Copy tất cả các phần tử của t1 vào ma trận đường t1=[]#Xóa t1 để phục vụ cho việc xét tầng tiếp theo for i in range( len(mtd)):#Xét ma trận đường. Làm tương tự như trên đến khi tìm được đường đầy đủ for j in range(h): for k in range(1,m/h+1,1): if a[j][k]==mtd[i][2]: addlist(t2,mtd[i]) t2.append(a[j][0]) t1.append(t2) t2=[] mtd=[] addlist(mtd,t1) t1=[] for i in range( len(mtd)): for j in range(h): if a[j][0]==mtd[i][3]: for k in range(1,m/h+ 1,1): t2=[] addlist(t2,mtd[i]) t2.append (a[j][k]) t1.append(t2) t2=[] mtd=[] addlist(mtd,t1) t1=[] for i in range( len(mtd)): for j in range(m): if b[j][0]==mtd[i][4]: for k in range(1,f+ 1,1): t2=[] addlist(t2,mtd[i]) t2.append (b[j][k]) t1.append(t2) t2=[] mtd=[] addlist(mtd,t1) t1=[] for i in range( len(mtd)): for j in range(n): if c[j][0]==mtd[i][5]: for k in range(1,e+ 1,1): t2=[] addlist(t2,mtd[i]) t2.append (c[j][k]) t1.append(t2) t2=[] mtd=[] addlist(mtd,t1) t1=[]#Đến đây ta đã tìm được tất cả đường đi từ server x đến các server khác for i in range(len(mtd)):#Duyệt tập hợp đường if(mtd[i][6]==y):#Lọc ra các đường đi có đích là y kq.append(mtd[i])#Thêm đường đi này vào kết quả trả về return kq#Trả về kết quả 7. Khối sắp xếp đường đi 7.1 Ý nghĩa Để tối ưu hóa hệ thống chúng ta phải chọn đường đi cho kết nối ở vị trí bên trái nhất. Chính vì thế sau khi tìm được tất cả các đường đi chúng ta phải sắp xếp các đường đi này theo thứ tự trái nhất đến phải nhất để phục vụ cho việc Optimizer 7.2 Giải thuật Để phân biệt các server chúng ta sẽ đánh số các chuyển mạch theo thứ tự từ trái sang phải bắt đầu từ 1. Do đó các server có số càng nhỏ càng nằm phía bên phải thì có trọng số càng nhỏ. Ta thực hiện sắp xếp theo cách: Duyệt tất cả các đường đi tìm thấy một cách tuần tự Với mỗi đường đi , tính tổng trọng số của đường đi đó Sắp xếp các đường đi theo tổng trọng số 7.3 Thực hiện Ta sử dụng một hàm phụ để tính tổng trọng số của đường đi a nào đó def tong(a): s=0#Khởi tạo tổng s for i in range(1,len(a)-1,1):#Duyệt các chuyển mạch trên đường đi a s=s+a[i]#Cộng trọng số của các chuyển mạch này vào s return s#Trả về s Thực hiện khối sắp xếp: def sapxepduong(a): #Đầu vào: #a: Tập hợp đường đi chứa tất cả các đường đi cần sắp xếp c=[]#Biến phụ c for i in range(len(a)): for j in range (len(a)):#Duyệt tập hợp đường a if (tong(a[j])>tong(a[i])):#Sắp xếp các đường đi bằng thuật toán sắp xếp thông thường c=a[i]; a[i]=a[j] a[j]=c return a 8.Khối kiểm tra đường đi 8.1 Ý nghĩa Sau khi tìm và sắp xếp các đường đi ta phải kiểm tra xem các chuyển mạch trên đường đi đó đã quá tải hay chưa để tránh trường hợp chọn phải đường đi đã quá tải cho kết nối. 8.2 Giải thuật Ta thấy trong đường đi gồm 7 chặng của chúng ta thì chặng thứ 1 và thứ 7 là server nguồn và server đích do đó chúng ta không cần quan tâm đến. Chúng ta chỉ cần quan tâm đến các chuyển mạch từ thứ 2 đến thứ 6 trên đường đi. Do chỉ số của ma trận bắt đầu từ 0 nên ta quan tâm đến các phần tử từ 1=>5 của ma trận đường 8.3 Thực hiện def kiemtra(a,b,c,d): #Đầu vào: #a: Ma trận đường chứa đường đi gồm 7 chặng #b: Ma trận chứa dung lượng hiện thời của cả hệ thống #c: Capacity của hệ thống #d:Dung lượng kết nối #Ta sử dụng cac biến k1=>k5 để lưu dung lượng các chuyển mạch sau khi đã cộng thêm dung lượng kết nối đầu vào if (a[1]==a[5]):#Vì phần tử thứ 1 và thứ 5 đều thuộc tầng top of rack nên ta phải xét trường hợp 2 chuyển mạch này trùng nhau k1=b[2][a[1]-1]+2*d k5=k1#Nếu phần tử 1 và 5 trùng nhau thì ta phải cộng vào dung lượng hiện thời 2 lần dung lượng link đầu vào do chuyển mạch đó được đi qua 2 lần else:#Nếu 2 phần tử nàyko trùng nhau k1=b[2][a[1]-1]+d#Cộng dung lượng link đầu vào cho cả 2 biến k1,k5 k5=b[2][a[5]-1]+d if(a[2]==a[4]):#Tương tự như trên k2=b[1][a[2]-1]+2*d k4=k2 else: k2=b[1][a[2]-1]+d k4=b[1][a[4]-1]+d k3=b[0][a[3]-1]+d #Đến đây ta đã có các biến k1=>k5 lưu dung lượng hệ thống sau khi cộng thêm dung lượng link đầu vào if (k1>c):#Kiểm tra có chuyển mạch nào có dung lượng vượt quá capacity ko return 0#Nếu có trả về 0 tức đường đi sẽ quá tải nếu thêm liên kết if (k2>c): return 0 if (k3>c): return 0 if (k4>c): return 0 if (k5>c): return 0 return 1 #Nếu tất cả các chuyển mạch đều có dung lượng nhỏ hơn capacity sau khi thêm liên kết thì trả về 1. 9. Khối cập nhật dung lượng hệ thống 9.1 Ý nghĩa Sau khi đã tìm được đường đi cho 1 yêu cầu nào đó thì yêu cầu này chiếm 1 phần dung lượng hệ thống do đó chúng ta phải cập nhật lại dung lượng của hệ thống 9.2 Thực hiện ktra=0 for k in range(len(mtd)):#Duyệt tập hợp đường if (kiemtra(mtd[k],mtdl,dl,ketnoi[i][j])==1):#Nếu kết nối ko quá tải yc.append(mtd[k])#Thêm yêu cầu vào ds yêu cầu được đáp ứng #Cập nhật dung lượng hệ thống #Cộng thêm dung lượng hiện thời với dung lượng link đầu vào(vị trí [i][j] của ma trận kết nối) mtdl[2][mtd[k][1]-1]=mtdl[2][mtd[k][1]-1]+ketnoi[i][j] mtdl[1][mtd[k][2]-1]=mtdl[1][mtd[k][2]-1]+ketnoi[i][j] mtdl[0][mtd[k][3]-1]=mtdl[0][mtd[k][3]-1]+ketnoi[i][j] mtdl[1][mtd[k][4]-1]=mtdl[1][mtd[k][4]-1]+ketnoi[i][j] mtdl[2][mtd[k][5]-1]=mtdl[2][mtd[k][5]-1]+ketnoi[i][j] ktra=1#Biến kt bằng 1 là đã tìm được đường thỏa mãn cho kết nối break#Chuyển qua yêu cầu tiếp theo if (ktra==0):#Nếu sau khi duyệt hết các đường mà biến ktra vẫn bằng 0 tức là tất cả các đường đi đã quá tải yctc=[mtd[0][0],mtd[0][6],ketnoi[i][j]] tc.append(yctc)#thêm yêu cầu vào danh sách từ chối 10.Khối tạo cây 10.1.Mục đích: - Biểu diễn các node sever,top-of-rack switch , aggregation, core trên 1 đồ thị. - Tạo ra 1 giao diện trực quan biểu diễn cấu trúc topology gồm 4 tầng tương ứng với 4 chuyển mạch chức năng . 10.2.Các công cụ hỗ trợ: - Phần mềm Python 2.7 -Tutorial về: Tkinter 8.4 reference: 1 công cụ để xây dựng giao diện cho Python và đã được tích hợp sẵn trong Python. Link: 10.3.Định dạng cây. - Cây gồm có 4 tầng :tâng core , tầng chuyển mạch tích hợp (aggregation) , tầng top-of-rack , tầng server. - Mỗi tầng gồm có các node hình chữ nhật để biểu diễn. - Các node có màu đen ,riêng đối với tầng server nếu không phát dữ liệu thì node sẽ được để màu xanh để phân biệt với các node còn lại. -Tạo ra liên kết giữa các tầng : các node được nối với nhau bằng 1 đường màu đỏ - Ở cây đã được Optimizer thì những node nào được tối ưu hóa không cần sử dụng sẽ có màu đỏ và những đường liên kết đã được tối ưu sẽ được nối với nhau băng nét đứt. 10.4. Cách thực hiện. 10.4.1.Xây dựng cây (khi chưa tối ưu hóa ). *Bước 1: Tạo khung hình cần vẽ: -Dùng lệnh canvas của Python để tạo ra 1 cửa sổ mới cho việc vẽ cây. Width và height là chiều rộng và chiều cao của khung hình cần vẽ bg = màu nền của khung hình (thường lấy màu trắng :white) canvas = Canvas(width=x, height=600, bg='white') canvas.pack(expand=YES, fill=BOTH) *Bước 2:Tạo hình chữ nhật cho node Để vẽ được hình chữ nhật ta cần có các thông số về 4 đỉnh.Do trong Python không có hàm tạo hình chữ nhật nên ta sẽ sử dụng hàm tạo đa giác với thông số là tọa độ 4 đỉnh để vẽ. D C n A B d Y X I -Chọn tham số n và d để xác định chiều dài và rộ