DAI HOC QUOC GIA
HA
NOI
TRirdNG
DAI HOC KHOA HOC
TlT
NHIEN
*********
DETAI
MOT NGHIEN
ClTU
VE MANG KHONG
TAC
NGHEN
MA
SO: QT-09-03
CHU
TRt
DE TAI: Ts. Le Trong
VTnh
CAC CAN BO THAM GIA: - Cn. Hoang
Qu6c
Hung
- Ths. Hoang Tuan Anh
DAI HOC QUOC GIA HA
NO!
TRUNG TAM THONG TIN
THlJ VIEN
oomoooo
^
HA NOI - 2010

MUC LUC
BAO CAO TOM
TAT 4
PHAN CHINH BAO CAO 9
I. Lai
ma
diu 9
II.
Kien true cua
mang chuyen mach 10
II.
1.
Cac thanh phan va kien
true
cua mang chuyen mach
11
II.2.
Mot so mang chuyen mach dac biet 13
III.
Truyen thong va Su khong tac nghen 16
111.1.
Cac kieu truyen thong 16
111.2.
Su tic
nghen 17
111.3.
Sir
khong tac nghen 17
111.4.
Cac

vande
ve mang khong tac nghen 18
IV. Dieu kien can va
dii
de
mpt
mang la khong tac nghen hoan toan 18
IV.
1.
Mot
s5
thuat ngu 18
IV.2.
Cac ky hieu va menh de 20
IV.3.
Dieu kien can va
dii
de mang khong tac nghen 23
V. Ket luan
vade
xuat 30
VI.
Tai lieu tham khao 32
PHU LUC 33
PHAN
CHJNH
BAO CAO
I.
Lai
md'

dSu.
Trong vai thap ky qua, anh huong
ciia
"mang" ngay cang ro ret trong viec to chirc he
thing may tinh. Mang may tinh la mpt he thing nhirng may tinh dpc lap dugc ket noi vai
nhau nhim dap ung cong viec chung
ciia
tl chuc. Mang dem lai nhimg thuan tien trong cupc
sing
nhu: cung cip phuang tien lien lac, chia se nhimg tai nguyen san co, cai tien su tin cay
cua dich vu, giam
thilu
chi phi Trung tim
ciia
viec dam bao ket noi mang thanh cong hay
that bai la cac thilt bi
chuyin
mach (switch). Mpt thilt bi chuyen mach (ca so) c6 nhiem vu
chuyin
mpt goi tin a mpt cong vao den mpt (hoac nhieu) cong ra. Khi nhu ciu ket noi mang
thip
(s5
lugng it), viec thilt kl cac mang chuyen mach (ket hgp nhieu thiet bi chuyen mach
CO
so vai nhau) de dam bao n6 co the chuyen dugc bat ky mot goi tin nao tir bat ky mot cong
vao chua diing den bit ky cong ra chua diing khac ma khong co giy ra hien tugng tac nghen
(cac goi tin dugc dinh tuyen sir dung cac lien ket khac nhau) la tuang doi de dang. Tuy nhien,
su
biing
no cua viec sir dung cac san phim va cong nghe lien quan den mang may tinh dac

biet la Internet ngay nay lam cho kich thuac
ciia
cac mang chuyen mach tang len rat nhieu.
Nhu ciu ket noi mang cang lan thi
kich
thuoc
ciia
cac mang chuyen mach cang tang. Mac
dii
vay, kich thuac
ciia
cac mang chuyen mach khong the tang vo han dugc, do do thiet ke vd xay
dung cdc mang chuyen mach khdng tdc nghen vai kich thuac be
Id
mot nhu cdu cap thiet de
dap img nhu ciu ket noi mang ngay cang tang hien nay. Han
niia,
nhu ciu ket noi mang ngay
nay khong chi tang ve so lugng ma con tang ve chat lugng nhu: bang thong lan hon,
toe
dp
cao han, it loi hon vi vay, cac mang chuyen mach dien (electronic) la khong
phii
hgp. Thay
vao do, cac mang chuyen mach quang (optical) da va dang dugc sir dung de thay
thi
cac
mang chuyen mach dien.
Mat khac,
"sir

khong tac nghen" phu thupc vao nhieu yeu to nhu: cac dang khong
tk
nghen, khuon mau
ciia
truyen thong, cac thuat toan sir dung de dinh tuyen,
sir
phu thupc vao
cac thiet bi vat ly nen viec thiet ke cac mang chuyen mach noi chung va chuyen mach
quang noi rieng khong tac nghen cang tra nen kho khan. Vi vay, vin dl khong tk nghen
trong mang chuyen mach dugc quan tim bai rat nhieu cac nha khoa hpc, cac cong ty, tip
doan trong nuac va ngoai nuac dau tu nghien cim. Do do, muc tieu cua dl tai nay la tim
hilu
ve cac bai toan trong viec phan tich, thiet ke va xiy dung mang chuyen mach quang khong
tac nghen.
II.
Ki§n true
cua mang chuyen mach.
Ly do diu tien de ra dai mang chuyen mach la tir nhu ciu ket noi
giiia
cac cap may dien
thoai. Ban diu, vai mot so lugng khong nhieu
ciia
cac may dien thoai, mot diy (dien thoai)
dugc noi
true
tiep giira hai may. Tuy nhien, khi so lugng
ciia
cac may dien thoai tang len va
gia truyen thong tren day (dien thoai) nay se tro nen qua tai va khai niem "switching"
(chuyen mach) da dugc ra dai. Thay vi ket noi

true
tiep moi cap hai may vai nhau, tit ca cac
may trong mot khu vuc nao do deu dugc ket noi den mpt trung tam chuyen mach (SC-
switching center). Cac may (dien thoai), day dan va bg chuyen mach tir nhieu mien khac nhau
ket noi voi nhau hinh thanh mpt mang (network) va dugc ggi la mang chuyen mach (SW -
switching network) - nhu trong hinh
1
duoi diy. Ngay nay, khai mang chuyen mach dugc ma
rpng trong viec ket noi cac may tinh trong mang may tinh, ket noi cac CPU, bp nho trong
may tinh song song, v.v
PC
PC
PC
o
Modem ,—'—•
r
^•K
A
Tc^ns dn
i
)
\
^
C^
C ouiiii uuic n
t
i
o
11
server

V/eb
server
PC 1
•.
TV'I
O
4J
«-
Ol
Reuio
le
access
server
-^-1-
i:;
HUB
I
c
I
PC
u
Hinh
1:
Mang chuyen mach
Mpt mang chuyen mach co the hoac
kit nli
vai mpt nhom nguai diing dugc gpi
la
mcxng
mot phia

(1-sided
network) hoac
kit nli
vai hai nhom gpi la
mcxng
hai phia (2-sided
10
network). Mac
dii
vay, cac ung dung va ly thuyet cho mang chuyen mach deu dugc nghien
cuu cho mang hai phia. Trong mang hai phia : diu vao x ket noi vai dau ra y thi se khong
giong nhu khi y ket noi vai
x,
trong khi chiing
la
giong nhau doi vai mang mpt phia. Noi
each
khac, mang mpt phia chi la truang hgp dac biet
ciia
mang hai phia. Do vay, de tai nay
chi tip trung nghien cuu ve mang hai phia va de cho ngan ggn, tu day ve sau, chung toi su
dung "mang chuyen mach" dong nghia vai
"mang
chuyen mach hai phia" neu khong c6 mpt
sir chi ro nao. Phin tiep se trinh bay cac thanh phin va kien tnic
ciia
cac mang hai phia.
11.1.
Cac thanh
phin

va kiln
true
cua mang chuyen mach
Phin nay trinh bay cac thanh phin chinh, cac khai niem va kien tnic mot mang chuyen
mach [1].
• Crossbar (hay switch element)
Crossbar hay switch element (SE) la thanh phin co ban nhit
ciia
mpt mang chuyen
mach. Crossbar la mpt nut trong mang chuyen manh. Mot crossbar gom co cac loi vao (in-
let) hay diu vao (input) va cac loi ra (out-let) hay diu ra (output). Mot crossbar vai n loi vao
va m loi ra dugc ki hieu la
X^m
ggi la no co ca
«
x m.
Hinh 2. Vi du ve mot crossbar 3x4
Ro rang, trong mpt crossbar, vai bat ky mpt loi vao roi (chua sir dung) nao
diu
c6
thi
ket noi tai bit ky mpt loi ra roi (chua sir dung) boi cac ket noi chua sir dung. Hai
kit nli
chung mot lien ket se giy ra
sir
ngan chan (block) lan nhau (cai nay dung thi cai kia khong
diing dugc nua va ngugc lai) va dugc ggi la tdc nghen (blocking). Hai
kit
nli sir dung cac
lien ket khac nhau se khong ngan chan lan nhau va dugc gpi la khdng tdc nghen (non-

bloking). Mpt mang co the thiet lip dugc moi ket noi sao cho khong co hien tugng blocking
xay ra dugc gpi la mang khdng tdc nghen. Nhu vay, crossbar la khong tic nghen.
• Mang chuyen mach
De phuc vu cho N cap ket noi, chiing ta mpt crossbar vai
A^
l6i vao va N
16i
ra. Neu
A^
dii
Ian thi viec thiet ke mpt crossbar nhu vay trong thuc te la khong kha thi bai gia thanh
11
ciing nhu do phuc tap cua no. De tranh phii thiet ke cac crossbar vai kich thuac lan nhu vay,
nguai ta thuong thiet ke mot mang chuyen mach bang each ghep nhieu crossbar co kich
thuac nho vai nhau theo mot kien
true
nao do, vi du nhu trong hinh 3 duoi diy.
Hinh 3: Vi du ve mot mang chuyen mach gom cac crossbar noi vai nhau
•
(A'^,
M)-network:
La mpt mang chuyen mach gom co
A^
loi vao va co M loi ra. Neu N
^
M
go\
la N-
network.
•

5-stage:
La mpt mang chuyen mach c6 s stage (tang). Moi mpt stage la mpt cot
ciia
crossbar.
Nhung crossbar
ciia
mpt stage (tang) thi se co ca tuong duong nhau.
Trong kien tnic nay, loi ra
ciia
cac crossbar a stage-i se lien ket tai nhirng
15i
vao
ciia
nhiJTig
crossbar
stage-{i+\).
Neu crossbar a stage-i c6 ca
-^njm,
•
Tang thir
/
c6
/-;
crossbar thi
ta luon co:
r,x
m,
=
r/.ix
/7,.i(bao

toan duang
links).Voi / =
l ^-l.
Cac s-stage c6 the xep chong len nhau va ggi la cac stack. Mpt mang chuyin mach
ting
quit dugc xem nhieu stack cua mpt kieu s-stage nao do. Vi du trong hinh 3, mang
gim
2
stacks cua 3-stage.
• Cach xay
dirng
mang theo kien
true
5-stage
So lugng cac crossbar trong cac ting
ciia
mot s-stage phai thoa man dieu kien:
ting
so
lli
ra
ciia
cac crossbar a ting
/
phai bang so tong so loi vao cua ting thu
/+!
vai
/
tir
1 din

s-l.
Do vay ta co the xiy dung cac s-stage nhu sau.
12
i) Gia su
A'ab^^cd
la
cac crossbar de xiy dung
2-stage,
khi do:
Ting stage-\ dung c crossbar ca
X^b-
Tang stage-2 diing b crossbar ca
Xcd
ii) Gia sir
Xab,
Xcd,
Xbe
la cac crossbar de xiy dung 3-stage, khi do;
Ting
stage-l
dung c crossbar co
X^^.
Ting stage-2 diing b crossbar
caXcd.
Ting stage-3 dimg d crossbar ca
Xbe
iii) Tong quit, de xiy dung s-stage diing cac crossbar :
Ting stage-l diing
is
crossbar co

^/^/^
.
Ting stage-2 dimg
12
crossbar ca
^^.
.
Tang stage-3 dimg
i^
crossbar ca
X
.
Ting stage-4 dimg
i^
crossbar ca
X^
.
Tang
stage-}
diing
z"
,,
crossbar
X
Ting stages diing
/^^,
crossbar
X-
• (t bit ky).
s't

11.2.
Mot 56 mang chuyen mach dac biet
Phin nay se trinh bay nhimg mang chuyen mach thuong dugc diing trong thuc tl va
nghien cuu
ly
thuyet [2].
• Mang
Clos
Trong
linh
vuc vien thong, mang
Clos
la mpt loai mang chuyen mach nhieu ting
(stage) dugc dua ra bai Charles Clos nam 1953, dung de trinh bay ly thuyet ve he thong
chuyen mach dien thoai nhieu ting. Mang Clos dugc diing khi cac yeu ciu mach chuyen doi
vat ly qua khi nang thong qua lan nhit cua mpt crossbar don.
LTu
diem chinh cua mang Clos
la dimg cac crossbar kich thuoc be (gia thap) de thuc hien chuyen mach tit ca cac yeu ciu
thay cho viec diing mot crossbar kich thuac lan (gia thanh cao).
13
crossbdis
mr
^
r
crossbars
Hinh 4: Mang Clos ba tang
Ciu tnic chuyen mach Clos gom ba ting, dugc the hien bai 3 so nguyen
n,
m,

r. Tang
diu tien c6 r phin tir chuyen mach (n x m) va tang thu 3 c6
r
phin tir chuyen mach {m x n).
Ting thu hai (tang giira) c6 m phin tir chuyen mach (r x r). Moi phin tir trong so r phin tir
chuyen mach cua ting diu tien dugc ket noi vdi tit ca cac phin tir chuyen mach cua ting thir
hai (mdi phin tir chuyen mach
ciia
ting diu tien co m loi ra. Moi loi ra dugc ket noi vai mpt
loi vao
ciia
timg phan tir chuyen mach khac nhau cua ting thu hai). Tuong tu nhu the, moi
phin tir trong so r phin tir chuyen mach
ciia
ting thu ba dugc ket noi vai tat ca cac phan tir
chuyen mach
ciia
ting thu hai.
• Mang Benes
Xuit phat tir mang Clos c6 nhieu hon 3 tang vai
m^n^2
,y tuang chinh
ciia
mang
Benes la xiy dung mpt mang lan dua tren cac thanh phin chuyen mach ( SE) vai thupc tinh
CO
kha nang sap xep khong tac nghen.
1
,p\y°-^^^/^.
I

Hinh 5: Vi du ve mang Benes
14
So dau vao va dau ra la N=rxn=2r. Vai nhiing mang c6
2\og2N
—
1 ting, moi ting
chua N/2 crossbar
2x2,
va su dung tong so
Mog^A^
—
N / 2 crossbar 2x2. Vi du, mang
Benes 8x8 (
A^
=
8), co
21og^5 — 1 =
5,
moi tang chira N/2=4 crossbar 2x2, va no sir dung
ting si
N\og2^
- N / 2
"=20
crossbar 2x2. Ba ting trung tam chua 2 mang Benes 4x4 nho
han, trong khi do a ting trung tam, moi crossbar 2x2 co the coi chinh no li mpt mang Benes
2x2.
Cho den nay, tieu chuin de danh gia chi phi
ciia
mpt khoi chuyen mach vin la so lugng
phin tir chuyen mach 2x2cin thiet de tao ra khoi chuyen mach do. Trong ciu

true
nay, suy
hao tren mgi duang din deu bang nhau, moi duang din se di qua
21og^7V — 1
phin tir
chuyen mach 2x2. Nhugc diem chinh
ciia
cau true nay la so lugng diem giao nhau
ciia
cac
ong din song theo yeu ciu lam cho cau
true
nay kho che tao trong cac mang quang tich hgp.
• Mang Banyan
La mpt trong nhimg kieu mang pho bien
ciia
mang ket noi da ting {Multistage
Interconnection Network- MIN). Mang Banyan dugc xiy
dimg
tir su lien ket
ciia
cac ting
ciia
cac SE
[3].
Mot SE 2x2 co ban co the dinh tuyen mpt khoi
(cell)
vao theo mot bit dieu khien
(dia chi dau ra). Neu bit dieu khien la 0, cell dugc dinh tuyen la dia chi cong cao hon, ngugc
lai thi no dugc dinh tuyen dia chi cong thip hon.

Liy vi du mang Banyan
SxS.Sn
lien ket cua 2 ting cua SE 2 x 2 co
thi
dugc lam bai
viec sir dung bit dau tien
ciia
dia chi ra de ky hieu cai SE dinh tuyen, va sau do su dung bit
cuoi ciing de xac dinh cong ra. Mang Banyan 8 x 8 co the xay dung mot
each
de quy bing
viec sir dung bit dau tien de dinh tuyen cell qua tang diu tien, hoac vao mang 4x4 thip han
hoac cao hon, va khi do sir dung 2 bit cuoi de dinh tuyen cell qua mang
4x4 dk phii
hgp vai
cong diu ra.
15
Hinh 6: Mang Banyan 3-stages
Noi chung, de xay dung mang Banyan N x N, tang thu n sir dung bit thu n
ciia
dia chi
diu ra de dinh tuyen cell. Cho N
=
2",
mang Banyan se chua
n
=
log2 N
ting, moi ting
chua N/2 SE. Mot MIN dugc gpi la tu dinh tuyen dugc khi dia chi diu ra hoan toan xac dinh

duang di qua mang.
Cong nghe mang Banyan la pho bien vi
sir
chuyen mach dugc thuc hien bai cac SE don
gian, cac cell dugc dinh tuyen song song, tat ca cac SE hoat dpng
o
ciing
toe
dp(nhu vay
khong han che kich thuoc
ciia
N va toe dp cong vao) va co the xay dung cau tnic chuyen
mach vai dung lugng lan mpt each de dang.
III.
TruyIn
thong va
SLF
khong tac nghen
III.1.
Cac kilu
truydn
thong
Trong mpt mang chuyen mach, mpt yeu ciu truyen thong se thupc mot trong cac dang
sau day :
• Unicast; Yeu cau truyen thong la truyen tin hieu tir mot loi vao den mot loi ra.
•
Broadcast:
Yeu ciu truyen thong la truyen tin hieu tir mot loi vao
din
tit ca cac lli ra.

• /-cast (hay multicast) : Yeu ciu truyen thong la truyen tin hieu tir mpt loi vao
dln/16i
ra.
Ro rang, day la kieu truyen thong tong quit nhat, vi unicast va broadcast chi la hai
trucmg
hgp dac biet
khi/= 1 va/=
A^(vai
A^
so loi ra cua mpt mang) tuang img
16
111.2.
SIP
tac nghen
De truyen tin hieu tir mot loi vao den mot loi ra, chung ra cin thiet lap mpt duong dan
tir loi vao den loi ra thong qua cac lien ket (link) giiia cac crossbar va cac crossbar dugc diing
de xiy dung mang. Cac crossbar la cac diem trung gian tren cac duang truyen tin hieu nen
chiing ggi la mot crosspoint.
Khi cac duang truyen tin hieu co mot lien ket
triing
nhau thi no dugc ggi la link-block
Khi cac duang truyen tin hieu c6 mpt crosspoint triing nhau thi no dugc gpi la node-block.
Khi truyen tin gap cac truang hgp nay nguoi ta gpi la xay ra hien tugng blocking.
Mpt mang co the thiet lip dugc mot duang truyen tin hien tir bat ky mpt loi vao chua sir
dung (roi) den bit ky mpt loi ra chua sir dung (roi) sao cho khong xay ra hien tugng blocking
dugc gpi la mang khdng tdc nghen va bai toan cho mang khong tac nghen dugc phat bieu nhu
sau: "Vai mpt kieu truyen thong cho truoc va kich thuac mang, hay thiet mpt mang khong
tac nghen sao cho so crossbar phai sir dung la it nhit".
111.3.
SiF

khong tdc nghen
Viec truyen tin tren mot mang deu lien quan den kieu truyen truyen thong, cau
true
cua
cac crossbar, va
each
xac lap cic duang di tir loi vao den (cac) loi ra. Do do yeu ciu vl su
khong tac nghen se phu thupc vao cac yeu to nay. Phin duoi diy se trinh bay cac dang (yeu
ciu) khong tac nghen thuong dugc nghien cuu.
• Strictly Non-Blocking (SNB)
Vai dang khong tac nghen nay, mang phai cho phep thiet lip dugc mpt duong truyin
tir bit ky loi vao nao chua dugc sir dung vai bit ky loi ra nao cung chua dugc sir dung ma
khong cin quan tim den trang thai
ciia
cac ket noi truac do trong mang.
•
Wide-sense
Non-Blocking (WSNB)
Vai dang khong tac nghen nay, mang phai cho phep thiet lap dugc mpt duang truyin
tir bit ky loi vao nao chua dugc sir dung vai bit ky loi ra nio ciing chua dugc sir dung ma
khong cin phai dinh tuyen lai cac ket noi dang
tin
tai; mang chuyin mach dang nay su dung
cac thuat toan dinh tuyen de dinh
tuyin
cho cac
kit
nli hien co sao cho dam bao khong xay ra
nghen cho cac ket noi tiep sau do.
• Rearrangeable Nonblocking (RNB)

Vai dang khong tac nghen nay, mang phai cho phep thilt lip dugc mot duang truyin
tir bit ky
loi
vio nao chua dugc su dung voi bit ky lli ra nao cung chua dugc sir dung nhung
17
DAI HOC QUOC GIA HA NOI
TRUNG TAM THONG
TIN THLf
VIEN
O0060OOOC:f9
cho phep dinh tuyen lai cho cac ket noi da ton tai. Viec dinh tuyen lai cac ket noi co the hoac
khong the dugc chap nhin con tuy thuoc vao ung dung vi chac chan cac ket noi se bi ngat
trong mot khoang thai gian nao do khi chung dugc chuyen mach sang duang din khac.
III.4.
Cac
vin d§
vd mang khong tic nghen
Nhu da trinh bay a tren, cac crossbar la khong tac nghen nhung khong the san suit
dugc mgi crossbar vai cac kich ca khac nhau trong khi do kich thuac cac mang chuyen thi
thuc te la hoan toan khac nhau. Hon nua, thuc te la khong the sin xuit dugc cic crossbar co
kich thuac bang dung kich thuoc cua mang chuyen mach. Vi vay, nguoi ta phai xiy dung cac
mang chuyen mach dua tren cac crossbar co san bang each xiy dung nhieu stages va nhieu
stacks. Mat khac,
nhiing
kien tnic huu dung cho cac mang trong thuc te da dugc chi ra, tuc la
each
thiet ke cac mang da dugc chi ra. Do vay, ve mat ly thuyet, su khong tac nghen thuong
dugc nghien cim nhu sau : Dua ra mpt kieu truyen thong, mpt kien
true
mang (clos, benes,

banyan ), kich thuoc
ciia
mpt crossbar, kich thuoc mang va dang tac nghen. Hay tim so
crossbar cin diing nho nhat de mang khong tac nghen. Noi
each
khac chiing ta phai tim so
stages va stacks cin phai sir dung. Mac
dii
vay, bai toan nay vin la rat kho, nen nguoi ta
thuong
CO
dinh so stages truac va chi tim so stacks.
Do thai gian c6 han, nen trong de tai nay, chiing toi chi tim hieu dieu kien cin va du (so
stacks toi thieu) de mot mang Banyan ngugc la khong tac nghen hoan toan cho kieu truyen
thong tong
quit/-cast.
IV. Dieu kien
cin
va du de mot mang la khong tac nghen hoan toan
IV.1.
Mpt
s6
thuat
ngu'.
De cho de trinh bay noi dung chinh, chiing toi trinh bay truoc cac khii niem lien quan
den mang khong tac nghen hoan toan:
• Mang
\og^(N,0,m)
De cin bang giiia chi phi va phin cung, phin lan cac mang chuyen mach dugc thilt ke
sir dung kien tnic da ting (multistages) va phin lan trong thuc the kieu kien tnic dugc sir

dung la Banyan ngugc. Vi vay, trong de tai nay chiing toi chi quan tim den kiln
true
da ting
kieu Banyan ngugc nhu dugc mo ta trong hinh 7. Moi Banyan ngugc dugc ggi la
moX
plane.
18
rjcoo 1
b'^
Td^-^^D^
1
A
}•
', ^.
/
<
V
V V
I
V ,'
t /
f '• '
' •••/ •:.
th
I):
m^^:j^
Hinh 7: Kien tnic Banyan ngugc BY" (5)
Hon nira, chung toi nghien
ciiru
kien

true
mang chuyen mach tong quit multi-log
d-dx^
voi nhieu stacks
ciia
cac planes theo chieu dpc nhu dugc mo ta trong hinh ve duoi diy.
HinhS:
Mang chuyen mach
log3('27,0,2^
19
Thiet ke nay dugc sir dung trong thuc te bai vi dp sau nho (dp phuc tap cua viec tim
duang di tir mpt cong vao den mpt cong ra) - 0{logdN) vai mpt mang chuyen mach c6
A'^
cong
vao va
A^
cong ra xay dung tir SE co kich thuac
\k
d x d. Do vay, chiing toi diing
\og^(N,0,m)de
chi mot mang chuyen mach multi-log
J-ary
vai m stacks.
• Kha nang Fanout (kha nang phan dau ra)
De ho trg multicast
(^idiy
f-cast),
mot mang
\og^(N,0,m)cdin
co kha nang fanout.

Mpt plane hoac SE
(i
x
J
co sa dugc ggi la co kha nang fanout neu bit ky mot anh xa 1-
nhieu tir mpt cong vao tai cic cong ra
ciia
no deu ton tai. Kha nang fanout cua mpt mang
\og^(N,0,m)
se dugc xem xet trong cac truang hgp
- Chi a ting dau tien duge cung cip kha nang fanout.
- Chi cac ting giira dugc cung cip kha nang fanout.
- Tit ci cic ting cung cip kha nang fanout.
Chu y: Neu nhu ciu fanout co a nhieu ting thi cang lam cho viec thuc hien no tra nen
phuc tap va ton han. Vi vay kha nang fanout can dugc xac dinh can than trong viec thiet ke
mpt mang chuyen mach.
• Tac nghen (block)
Tac nghen thuong dugc xem a mot trong hai dang duoi day:
o Tdc nghen lien ket
(Link-block
):
chi co mpt yeu ciu dugc phep sir dung mot
link a mot thai diem (trong chuyen mach dien).
o Tdc nghen
niit
(Node-block): chi cho phep mot yeu ciu dugc sir dung mpt SE
a mpt thai diem.
IV.2.
Cac ky hieu va menh
d§

Cho bit ky so nguyen duang
I,deo:
+[l]:
ky hieu
tip {1, ,/}
+
Z^
: ky
hieu
tip
{0, ,d-\} va cung
dugc xem
la
cac ky hieu
t^-ary.
+
Z^
:
ky hieu tap tat ca cac chuoi
d-axy
dp dai /.
20
+ ^
: ky hieu chuoi / ky tu
Z>
e
Z^.
+|s|:
ky hieu dp dai
ciia

chuoi s d-ary
(|31|=
2).
+
s-
ky hieu day con
s-
-ciia
mot chuoi s =
Sj Si G
Z^
Khi i >
j
quy uoc
S-
la
I J I J
i j
day rong.
Cho N =
d"
chung ta xem xet mang
\og^(N,0,m)
la mang gom m stacks
ciia
d-ary
BY"
(n) {Banyan ngugc) vai
A^
dau ra va N diu vio.

Danh so cho dau vao va diu ra
ciia
BY~ (n) la cac chuoi d-ary co dp dai n. Dac biet,
moi diu vao
x^Tf^
va diu ra
J^
GZ^
co dang
x =
x^ x^,y
=
yj y^
vox
x^^y.^Tj^,
\/i G
[n].
Tuong tu viec danh so trong cac SE
c/xc/trong
moi ting
ciia
n ting
ciia
BY"
(n) voi
chuoi
£^-ary
dp dai
n-I.
De thiy rang mpt diu vao x (mot diu ra y)

la
dugc ket noi voi SE co
nhan
x^ ^_j 6
ting diu tien
(y^
^_j a
ting cuoi).
Chung ta co the de dang thay rang tien to cua
y^
^_^
la dam nhin tien to cua
x^ ^_j
tren duang di tir x tai y. Tong quit, duang di duy nhit tir mot diu vao x tuy y tai mot diu ra y
tiiy
y chinh xac la nhu sau :
Input
X
Stage-l SE
Stage-2 SE
Stage-3 SE
Stage-n SE
Output y
XjX2 X^^_jX^
XjX2 X^_j
yi^2-^n-l
yiyi-yn-i
yiyi'-yn-iyn
21
Bay gia ta xem xet hai yeu ciu unicast

{a,
b) va
{x,y).
Trong truang hgp tac nghen mit,
hai yeu cau nay khong the di qua ciing mpt stack
ciia BY'^(n)
khi va chi khi hai duang di
tuong img giao nhau a vai SE a ting giira (neu chiing dugc dinh tuyen qua ciing mot stack ).
Chinh xac hon, (a,b) va (x,y) dugc gpi la tac nghen mit vai nhau khi va chi khi co
j G
[n] sao cho
by ^_j =
y^
j_j
va
3.j
^_j = x^ ^ ^ .Trong
truang hgp nay, hai duang di giao
nhau a ting
j ciia
SE. Nen
chii
y rang hai duong di
ciia
hai yeu ciu co the giao nhau tai nhieu
hon mot SE.
Trong mot mang
\og^(N,0,m),
hai yeu ciu tac nghen mit voi nhau phai dugc dinh
tuyen qua cac ban copy

BY"
(n)^ac
nhau. Cho hai
chudi
bit ky u,v
G
Z^
.
- PRE{u,v) ky hieu tien to chung dai nhit cua u va v.
-
SUF{u,v) ky hieu hau to chung dai nhat
ciia
u va v.
• Menh
del:
Cho (a,b),(x,y) la
2yeu
cdu unicast trong mot mang
log^(N,0,m).
Khi do 2 yeu cdu
goi la tdc nghen niit khi vd chi khi
\ SUF(ay
„_y,X/
^_J|+|PRE(b^
^-z^Y/
n^/)\^^-
^ •
Chitng
minh:
Hai yeu ciu la tac nghen mit khi va chi khi chiing dimg chung mot crossbar.

Xet 2 yeu ciu (a,b) va (x,y).
Hai yeu ciu nay tac nghen
niit
khi va chi khi co mpt vai so
j e
[n] ma
b^
_^ =
y^
,
va a
^^j =x ^_j
(Trong truang hgp nay hai duang dan giao nhau a
stage-j
SE).
Hay
|SUF(a,^_y,x,^_J|+|PRE(b,„_,,y,,,_y)|>^-7
(dpcm).
• Menh dl
2;
Cho
(a,b),(x,y)
la
2yeu
cdu unicast trong mot mang
\og^(N,0,m).
Khi do 2 yeu cdu
goi la tdc nghen lien kit khi vd chi khi
| SUF(a/^,_/,Xy ^,_/)|+|PRE(by
^,_y,y/^_y)|

>
^.
Chung minh:
Hai yeu ciu li tic nghen lien ket khi va chi khi chiing diing chung mpt lien ket trong
BY'Y^y'Cnlu
chiing dugc dinh tuyen qua ciing mot ban copy ).
22
Tuang tu chimg minh menh de 1, xet hai yeu ciu (a,b) va (x,y).
Hai yeu cau nay tac nghen lien ket khi va chi khi c6 mot vai so j
G
[A?]
ma
b/ ,w
=
y/ ,-/,
^j „-i
=
^j,.n-i ^ ^Lj =
YL.J
Vi
a^.^y
^_y -
x^^y
^_^.
Hay tuang duong vai dieu kien
by =
y^
va a
^_y
=

x
^_y.
Hay
I
SUF(ay
„_y,Xy
,_y)|+|PRE(by
„_y,yy
^_y)|
> n (dpcm).
IV.3.
Didu
kien
cin
va du de mang khong
tSc
nghen
Phin nay se chi ra cic dieu kien cin vi
dii
dl mang
\og^(N,0,m)
la khong tic
nghen hoan toan [3].
Truang hap
1:
Chi co ting giiia c6 kha nang fanout
•
Dinhlyl:
Chor
=

[\ogJJ
vdmjnj,d) =
f(d'^^^-\)^d"~'^~^\
Dieu kien cdn va du de mang
\ogj(N,0,m)la
f-cast
hoan todn khong tdc nghen
trong truang hap tdc nghen nut la
m >
mjnj.d)
khi f <
c/""'
-
d"'^
m >
m„,(n,d"~'
-
d"'^,d)
khi f >
d"''
-
d"-'+
]
• Djnh ly 2 :
Chor^[\ogJ] vdmjn,f,d) =
f(d
'
-l) + d
'
.

Dieu kien cdn vd
dii
de mang
\og^(N,0,m) Idf-cast
hoan todn khdng tdc nghen trong
truang hap tdc nghen lien ket
Id
m
>mj^(n,f,d)
khi f
<d''~
m>mii^(n,d"'
,d)khi
f >
d"~
Viec chimg minh dinh ly
1
va 2 la tuong tu nhau nen a diy chiing toi chi trinh bay cich
chimg minh dinh ly
1.
23
Chicng
minh:
Gia su mang da thiet lip duang di cho mot
si
tip
5?
cac yeu ciu . R =
(x,Y)
la mot

multicast mai yeu ciu tuong thich vai tinh trang mang hien tai, khi x la mot vai diu vao va
Y la mot tap con
ciia
/ diu ra, / < /. De mang la khong tic nghen hoan toan, chiing ta phii
tim dugc mpt bin copy
ciia
BY"
(n) dl dinh
tuyIn
R. Ky hieu
b(*}{)
la
si
cac yeu ciu
trong
y{
ma tac nghen mit R (vi du truang hgp khong the dugc dinh
tuyIn
qua ciing ban copy
cua BY"
(n)voi
R). Khi do R co kha nang dinh
tuyIn
khi va chi
Wx
m>
b(y{) +
1.
(*)
Diu tien, quan tim toi truang hgp khi / <

d"'^
—
d"~^
.
Chiing ta tim giai han tren
cho
b^yi)
.Gioi
han tren B se phu thuoc vao
??
va
R.
Khi do, m>B + l la dilu kien
dii
dl
mang
logj(N,0,m)\a
hoan toan khong tac nghen.
Bai vi ting diu tien khong co kha nang fanout, mpt yeu ciu
{x,Y)Xac
nghen mit R khi va
chi khi
CO
mpt so y
G Fma
yeu ciu unicast (x,y) tac nghen
mit
R. Vi vay, khong mat tinh
tong quit, chiing ta gia sir rang
9?

chiia toan bg cac yeu ciu unicast.
Viet
/={y , ,y
}. De cho mpt yeu ciu (x,y) tac nghen
mit
R,
(x,y) phai tac
(p)
nghen niit yeu ciu
(^x,
y ) cho mpt so 1 <
p<l.
Nx
vay chiing ta se thio luan chi tiet
tren do {x,y) c6 the tac nghen mit
(
x, y
J.
Cho moi
/
G
{0, ,n
-
7}
, ky hieu
X^
la tip cac dau vao x khic x ma
Xy
„_;
va

X/ n~i
CO SO
hau to giong nhau voi dp dai chinh xic la
i.
Hay co the dinh nghia nhu sau:
X,
:=
{x
G
Z:
-
{x} I
SUFrx,,,,_y,x/, ;;
=
/}.
fp)

-
~^p^
Tuong tu, cho mSi
j
e
{0, ,n
-
1} ,ky
hieu
7.
la tap cic diu ra khac y cai ma
CO SO
tien to giong nhau voi y co dp dai chinh xac liy. Cu the la:

Y^/^
{y G
z:
-
{y''} I PREry;,.,._y,7'^, _J =
j}
24
Theo menh dl 1,
{x,y)
tic nghen
niit (x,y
) khi va chi khi (x,y)
G Xp(.Y^j^^vox
i,
;:i
+ j>n-l
Vi vay ma {x,y) tic nghen mit voi (x, Y) khi va chi khi (x,y)
G
X,x7|^''cho
i,JG{0, ,n-I}
va I < p<l cho i +
j>n-1.
Cho I
=
7f^
ky hieu tip dau vao
O
=
7f^
ky hieu tip diu ra.

Xiy dung do thi hai phia
Gj^=(
I
KJ0,E
) la hgp
ciia
tit ca cac do thj hai phia
X-xYj
ma
i-\-j>n
—
l. Khi do (x,y) tac nghen mit R khi va chi khi (x,y) la mpt canh
ciia
G^
.Moi
tip yeu ciu trong R tac nghen
niit
R phai la mpt cap ghep
ciia
Gy^,
de cho
?J
la mpt
tip yeu ciu gii tri. Vi vay ma
b(^) < v(Gn)vox v(Gf^)ky
hieu la so cap ghep
cue
dai
trong
Gf^.

m> max
v(Gj^)-\-l
{\)
R an
1-cast
rcques/,I<f
la dieu kien cin de mang
\og^(N,0,m)
la/-cast hoan toan khong tac nghen.
x(Gn)
la kich thuoc toi thieu bao
phii
dinh trong
G^
, khi do
T(GJ^)
=
v(Gj^)
theo
n-r
-1
dinh
ly
Konig-Egevary [4]. Cho
j = [
j .
Chii
y ring trong truang hgp nay thi r <n- 2 . Chinh vi vay ma
j>
1.

De dang xic dinh rang tip bao
phii
cac dinh
ciia
Gj^
la:
Vi
I
X,
IH
Y/^^
\=
d"~'
-
d"~'~'
cho mpi
/,
chiing ta co :
\C\<(d'^'
-d"-'-'
+
+
d^
-d') +
l(d^
-d^-^
+
+
d^
-d')

25
<(d"-^-l+f(d^-l)
= mjn,f,d)-l
N\v^yv(GJ
=
x(G,)<\C\<mJn,f,d)-l
Theo (1) bo de dugc chiing minh.
(**)
Thii
hai ta quan tam toi truang hgp
/
>
d"~'
—
d"~
+
1.
Nlu
/<
J""^-^""^khid6
bC^)
chi
CO thi
lan nhit la
mjn,2"'^-2"~\d)-l
bai phan tich truac va thuc te rang
m^^(n,
f
,d)
li

mpt ham khong giam trong/
NIU
/ >
(^""^
-
(^""^
-h
7,
thi
si
diu ra
khong
su
dung
lan
nhit
la
d"-l<d"
-d"-^
+d"-'
-I.
V\vayb(dl)<d"-d"-^
^d"-'-l =
mJn^d"-^
-d"-\2)-l.
Dinh ly dugc chimg minh.
Truang hop 2: Ci ting diu tien va ting giua co kha nang fanout
•
Dinhly3:
Cho

r
=[iog^
fj.Diiu
kien cdn
vd
du
de
mang
\og^{N,0,m)ld
f-cast
hoan todn
khdng tdc nghen trong truang hap tdc nghen nut
la m>
m^^^{n,f,d)
.
•
Dinh ly 4
:
Cho
r
=•
Wog^
f^.Diiu
kien cdn vd
dii
de mang
log^(N,0,m)ld
f-cast
hoan todn
khdng tdc nghen trong truang hap tdc nghen lien ket la

m>m^f^(n,f,d).
Chirn^
minh:
Gia sir mang da thilt lap duong di cho mot so tip
9^
cac yeu ciu.
R
=
(x,Y)\a moxf
cast mai yeu
ciu
tuong thich voi tinh trang mang hien tai,
khi x li
mpt
vai diu
vao
va
Y =
{y
, ,y ^lampt
tip con
ciia
hiu
het/diu
ra. Cho moi
/
G/"//,
phan
(x,y )c6
thi

dugc dinh
tuyIn
phu thupc vao
tit ca
(x,y
)
khic
mi j
^ /
va
j
G
[I].
Boi
vi ca
26
hai tang deu co kha nang fanout. Vi vay khong mit tinh tong quit ta gii sir rang
Ychx
chua
mpt diu ra y vi du
7? =
(^x,y^.
Khong giong nhu chimg
mirih
dinh ly 1 chiing ta khong the gii sir rang tip yeu ciu
trong
9{
la cic tip unicast, bai vi moi yeu ciu R trong
5R
co the dugc dinh tuyen qua vai bin

copy khic nhau BY~ (n). Tuy nhien chiing ta co the bo qua cic nhinh
ciia
R ma tai do
khong
tie
nghen nut
7?
.
Nhu vay cho moi yeu ciu 7?
=
(^x,{y
, ,y
JJ^^l
chiing ta co the gia sir rang
(x,y
) tie nghen
mit
7? cho mpi
i<l.
Tuong tu chung minh dinh ly
1
cho moi 0<i<n- 1 dinh nghia :
X,
:=
{X
e
Z^
-
{xj
|

SUF^x,
„_„x/,
yj =
i}
vi cho moi 0
<
j
<n —
1 :
r^.
;=
{y
e
Z:
-
{y;
I
PREry,
„_py,„„_;;
=
77
Chu y ring tip
X^
li tip roi phu thupc lan nhau.
Y
la tip rai phu thupc lan nhau.
Yionnn?i,\X,\=\Y,\^d"~'-d"
yi
—(0)
—(I)

Theo menh dl 2 cho mpi yeu ciu R
=
(x,{y
, ,y })e9{
va cho mpi
p^flj,
no phii la truang hop (x,y
^
y*
^ ^, x Yj cho
moi
iJ
mai
+
j>n-l.
Gpi
Gn
la dl thi hai phia la hgp
ciia
tit ca
X^
x
Y^
vox
i^-
j>n-
1.
Khi do mpi yeu
ciu 7?
G ?{ phii

hgp duy nhit vai mpt tip
ciia
cic
canh/lien
thupc vai ciing dinh vao.
Tren phia diu ra, khong co dinh ra nao xuat hien hon mpt lin trong
9i.
Cho
bC^i)
la
si
canh trong
G^
cii ma
?? phii
hgp voi. Khi do, m >
maxZ?(^9^^
-h 7
la
hiln
nhien
dii
dl
dinh
tuyIn
9?.
Trong truong hgp xau nhat, moi nhanh (duong)
ciia
mdi yeu ciu trong
9^

duoc dinh tuyIn qua
mpt ban copy khic
ciia
BY"V^/
27
Biy gia ta ky hieu
Vf(Gj^)\a
kich thuac toi da cua mot tip con S cua cac canh
ciia
Gj^
thoa man dieu kien sau:
a)
m6i
diu vao la lien thupc vai hiu
hit/canh
trong S.
b) moi dau ra la lien thupc voi het cic canh
1
trong S.
(chu y rang
V^^f^Gy^^la
so cap ghep
ciia
v(G)). Khi do tir phin tich tren ta co
Z?(^9?^<
v.f^Gy;
J.
Vi vay
m>m?iXV JGr.)+
1 la dilu kien cin dl mang

\ogJN,0,m)
J R
^
la hoan toan khong tic nghen trong truang hgp tic nghen mit.
Xiy dung mpt luong mang
Dj^
nhu sau:
Mang
CO
mpt nguon
s,
mpt dich
/,
va tip dinh X
^JY
vox
Co mpt canh tir dinh nguon s tai mpi dinh x
G
X
vai khi nang thong qua/
Co mot canh (x,y) voi khi nang thong qua la 1 tir
A'
tai
7
khi va chi khi
(x,y)GX,xYj,z +
y>^-7.
Culi
ciing
CO

mot canh tir moi y
G
Y voi kha nang thong qua li
1
tai dinh dich
/.
Vi vay
''phdn
giira
" ciia
luong mang chinh xac la
Gj^
vox s,t phu hgp hai ben.
Cho mpi tip S chiia cic canh cua
G^
thoa man dieu kien (a),(b) a tren, de thay rang c6
su tuong ling mpt
lulng
nguyen vai gia tri chinh xic ca
ciia
S. Chinh vi vay,
151
la gii tri
lulng
cue dai trong
Dj^,ky
hieu la
MAXFLOWf^Dy^^,
chinh bing gii tri kha nang thong
qua cue

tilu ciia
lit cit s,t trong
Dj^,
ky hieu la
MINCUTf^T:)/^;.
Vi vay
V (G ) <
MINCUT(Z)y^).
Trong do
v^(G/^)la
kha nang thong qua
ciia
lit cit s,t bit ky
trong
Dj^.
Cho i
= f / " ^ •
De y den lit cat
s,
t
trong
Dj^
nhu minh hoa trong hinh
^
2
28

o
n-j-2
Hinh 8 : Lit cat s,t trong chiing minh.

n-I
n-I J
({s}^[/iX,.j[}Y„ U X[JY,^{t})
i^O
t=j+/
i^n-j-l
i^O
Khi nang thong qua
ciia lit
cat nay chinh xac la
n-I
n-I
Z
f\X.\+T\Y.\-rnJn,f,d)-l
Vi vay
m
>
m^^(n,f,d)
la dieu kien cin.
Truang hop
3:
Chi co tang diu tien co kha nang fanout
• Dinh ly 5:
Cho r =
[logoff .
Dieu kien cdn vd
dii
de mang
\og^(
N

,0,m) Id feast
hoan todn
khdng tdc nghen trong truang hap tdc nghen nut
Id
:
d'^-d''-^
+1
m>d"
khi f >
n-I
m>df +
d''-'
kh
d
d
>f>d
n-3
m>m;jnj,d)
khi
d'"'
>
f
>d'
,r
<n-4.
Dinhly6:
29
Cho r =
flog^fj .Dieu
kien cdn vd du de mang

\og^(N,0,m)la
f-cast
hoan todn
khdng tdc nghen trong truang hap tdc nghen lien kit la :
m>d"
-1 khi f>
d
m>df
+
d"-'-l
khi
^" '^" ^^
>f>d"-\
d
m
>
ml(n,
/,
d) khi
d'^^
>f>d\r<n-4.
Cich chimg minh hai dinh ly nay ciing tuong tu nhu tren.
V.
Kit
luan va
d§ xuit
Trung tam
ciia
viec dam bio ket noi mang thanh cong hay thit bai la cac thiet bi chuyen
mach (switch). Mot thiet bi chuyen mach (co so) co nhiem vu chuyen mpt goi tin

6
mpt cong
vio den mpt (hoac nhieu) cong ra. Khi nhu ciu ket noi mang thip (so lugng it), viec thiet ke
cic mang chuyen mach (ket hgp nhieu thiet bi chuyen mach co so voi nhau) de dam bao no
CO
the chuyen dugc bit ky mot goi tin nao tir bit ky mpt cong vao chua diing den bit ky cong
ra chua diing khic ma khong giy ra hien tugng tic nghen (cic goi tin dugc dinh tuyen sir
dung cic lien
kit
khic nhau) la tuong doi de dang. Tuy nhien, su biing no cua viec
sir
dung
cic sin phim va cong nghe lien quan den mang miy tinh
die
biet la Internet ngay nay lam
cho kich thuoc
ciia
cac mang chuyen mach tang
len
rit nhieu. Nhu ciu ket noi mang cang lan
thi kich thuoc
ciia
cac mang chuyen mach cang tang. Mac
dii
vay, kich thuoc
ciia
cac mang
chuyin mach khong the tang v6 han dugc, do do thiet ke vd xay dung cdc mang chuyen mach
khdng tdc nghen vai kich thuac be
Id

mot nhu cdu cap thiet de dip
ling
nhu ciu ket noi mang
ngiy cang tang hien nay. Vi do la mpt vin de da dugc nghien cuu trong de tai niy vai nhung
ket qua dat dugc la :
1.
Trinh bay
ting
quan vl mang khong tic nghen, cac dang khong tic nghen.
2.
Ap dung ly thuylt do thi vio nghien cuu phin tich dieu kien cin de mpt mang
\og^{N,0,m)
la hoan toan khong tic nghen.
3.
Nghien cim
ting
quit hon nhirng
kit
qua truoc diy:
• Cic SE la d-ary kich thuoc dxd tong quit hon SE kich thuoc 2x2;
30
• Truyen thong la/ cast bao gom ca unicast
{f=\)
va broadcast
(f=
N).
• Ca tac nghen nut va tac nghen lien ket deu duge xem xet theo mot cich hgp
nhit.
• Tit ca su ket hgp cic dieu kien fanout
diu

dugc xem xet.
Do thai gian nghien cuu c6 han nen van con nhiing vin de chua dugc de cap toi. Cu
thi:
• Phin tich cho cac kieu khong tic nghen khacla RNB vi WSNB.
• Kien tnic mang la
log^(N,p,m)
- tong quit hon.
Va day la nhiing huong co the tiep tuc nghien cim trong tuong lai.
31