Báo cáo Project 1 Optimizer
Mục Lục
Mục Lục...................................................................................................1
I.Tổng quan về chương trình.................................................................2
1. Mục đích của chương trình:......................................................................................................................2
2. Giới thiệu chung về Optimizer và thuật toán sử dụng..............................................................................2
3. Giới thiệu chung về chương trình.............................................................................................................2
1.Khối nhập dữ liệu đầu vào.........................................................................................................................5
2. Khối tạo ma trận bit rate...........................................................................................................................6
3. Khối tạo ma trận công suất.......................................................................................................................8
4. Khối tạo ma trận kết nối.........................................................................................................................10
5. Khối tạo 3 ma trận thể hiện kết nối........................................................................................................11
6. Khối tìm đường cho kết nối ...................................................................................................................19
7. Khối sắp xếp đường đi............................................................................................................................27
8.Khối kiểm tra đường đi............................................................................................................................28
9. Khối cập nhật dung lượng hệ thống.......................................................................................................31
10.Khối tạo cây ...........................................................................................................................................32
11. Khối in kết quả:.....................................................................................................................................45
1
Báo cáo Project 1 Optimizer
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

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 x
y
def mu(x,y):#Khai báo hàm
s=1#Khai báo s
4
Báo cáo Project 1 Optimizer
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")
5
Báo cáo Project 1 Optimizer
dl=float(raw_input("Nhap capacity cua he thong"))

• 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
7
Báo cáo Project 1 Optimizer
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

return a
9
Báo cáo Project 1 Optimizer
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):
10
Báo cáo Project 1 Optimizer
#Đầu vào:
#bit: ma trận bitrate

• 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:
12
Báo cáo Project 1 Optimizer
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:
13
Báo cáo Project 1 Optimizer
Do đó ta có giải thuật:

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
15
Báo cáo Project 1 Optimizer
• 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
16
Báo cáo Project 1 Optimizer
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

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
18
Báo cáo Project 1 Optimizer
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.
19