Trả lời câu hỏi ôn
tập
Chương 1
Câu 1: Lý thuyết độ phức
tạp-Ý nghĩa ?
Khái niệm độ phức tạp gắn với
khái niệm thông tin
-Lý thuyết tính toán: Độ phức
tạp của một vấn đề là số bước
giải quyết vấn đề bao gồm độ
phức tạp thời gian và độ phức
tạp không gian.
Lý thuyết thông tin: Độ phức
tạp Kolmogorov mô tả tập các
đặc tính của đối tượng và là độ
dài ngắn nhất mô tả hữu hiệu
đối tượng.
- Số bước cần thiết để giải
quyết bài toán chính là độ
phức tạp thời gian và là một
hàm của đầu vào, số lượng tài
nguyên không gian sử dụng
trong thuật toán hay bộ nhớ là
độ phức tạp không gian tính
toán.
Ý nghĩa của đọ phức tạp:
- Việc phân tích các mô hình
thông qua đồ thị sẽ giúp ta có
được các giải thuật tốt nhất
cho các bài toán liên quan tới
độ phức tạp của hệ thống, nhất

biệt của khe thời gian được ấn
định cho nguồn tin phía phát
và nguồn tin phía thu là một
yếu tố yêu cầu có sự chuyển
đổi nội dung thông tin từ khe
thời gian này sang khe thời
gian khác trong cùng một
khung, đó chính là quá trình
trao ñổi khe thời gian nội TSI.
Một cơ cấu sử dụng chuyển
đổi TSI được minh hoạ trên
hình dưới đây, các khối thiết bị
chính gồm có:
1
n
2
0 n 0
n
W r i t e
R e a d
R A M
0
n
0
n
0
n
0
n
1 4

dung thông tin và tuỳ thuộc
vào nguồn tài nguyên của hệ
thống, khối xử lý trung tâm sẽ
đưa các dữ liệu điều khiển tới
khối điều khiển CM nhằm sắp
xếp vị trí chuyển đổi của các
khe thời gian. Để đảm bảo tốc
độ luồng thông tin đầu vào và
đầu ra, trong cùng một khoảng
thời gian bộ nhớ lưu đệm phải
thực hiện đồng thời hai tác vụ
ghi thông tin vào và đọc thông
tin ra. Theo nguyên tắc trao
đổi khe thời gian nội TSI, độ
trễ tối đa của thông tin trao đổi
không vượt quá thời gian của
một khung Td (max) = (n-
1)TS < 125às.
Câu 3 :Định lý clos-Chứng
minh định lý?
-KN: Ma trận chuyển mạch kết
nối 3 tầng không tắc nghẽn khi
và chỉ khi số kết nối trung gian
r2 ≥ n + m -1. Trường hợp đặc
biệt khi n=m thì r2 ≥ 2n-1.
-CM:
Mô hình ghép nối có liên kết
đầy đủ 3 tầng chuyển mạch
được thể hiện trên hình 2.9
(a). Ma trận chuyển N đầu

ra.
Ma trận chuyển mạch không
tắc nghẽn hoàn toàn khi đường
vào thứ n của tầng A
Kết nối được đường ra thứ m
của tầng C, dẫn đến số lượng
khối chuyển mạch trong B
Tối thiểu phải dư 1 khối cho
đường dẫn cuối cùng này. Hay
nói cách khác số lượng liên kết
tối thiểu r2 ≥ (n-1) + (m-1) +1
= n + m -1.
Nếu ma trận chuyển mạch là
ma trận vuông (N=M), (n =
m) và (r1 = r2), ta có số lượng
điểm kết nối chéo là:
C = 2nr2 + r12r2 = 2n(2n-1)
+ r12 (2n-1) = (2n-1) ( 2N +
N2 ∕ n2 )
Khi kích thước của trường
chuyển mạch lớn, n lớn ta có
thể tính số lượng điểm kết
Nối chéo C xấp xỉ theo công
thức 2.4 sau.
C ~= 2n (2N + N2∕n2 )= 4nn +
2N2∕n
Để tối ưu số điểm kết nối
chéo, lấy vi phân C theo n:
(dc/dn) và cho kquả tiến tới 0
Ta có

- Thanh ghi trạng thái là sơ đồ
ánh xạ trạng thái hiện thời của
các kênh được chọn (bit
1 thể hiện trạng thái rỗi của
kênh, bit 0 thể hiện trạng thái
bận của kênh)
-Thanh ghi mặt nạ là một logic
nhị phân có độ dài bằng thanh
ghi trạng thái, trên đó tồn tại
02 bit có giá trị 1 và còn lại là
các bit có giá trị 0. Thanh ghi
mặt nạ có nhiệm vụ lựa chọn 2
khe thời gian rỗi (đầu vào và
đầu ra) cho kết nối.
3 thuật toán thường được sử
dụng trong cách thức di
chuyển mặt nạ gồm: Ngẫu
nhiên – liên tiếp, cố định- liên
tiếp và phương pháp thử lặp
Phương pháp ngẫu nhiên -
liên tiếp: phương pháp này
dựa trên nguyên tắc tìm
kiếm ngẫu nhiên một khe thời
gian rỗi, nếu khe thời gian đầu
tiên chọn ngẫu nhiên không
thoả mãn yêu cầu, hệ thống
dịch chuyển liên tiếp trong
toàn dải nhằm tìm khe thời
gian thoả mãn yêu cầu.
Phương pháp này tạo ra hiệu

I-Trường chuyển mạch không
gian số:
Nguyên lý chuyển mạch không
gian S
Cấu trúc chức năng:
Tầng chuyển mạch không gian
số được cấu tạo từ một ma trận
chuyển mạch mxn và một bộ
điều khiển khu vực:
Ma trận chuyển mạch gồm: m
đầu vào và n đầu ra trong đó,
lối vào tương ứng với các hàng
và lối ra tương ứng với các cột.
Tại giao điểm của hàng và cột
là các tiếp điểm chuyển mạch
(AND hoặc logic 3 trạng thái).
Các tiếp điểm này được điều
khiển bởi bộ điều khiển khu
vực (LOC) qua hệ thống
đường BUS.
Bộ điều khiển khu vực gồm:
Bộ đếm khe thời gian (TS –
COUNT) đếm các khe thời
gian đồng bộ đưa vào bộ chọn
tín hiệu.
Bộ chọn tín hiệu (SEL) chọn
tín hiệu ghi đọc cho C-MEM.
Bộ nhớ C-MEM lưu địa chỉ
liên quan tới các tiếp điểm
chuyển mạch tương ứng với

tương ứng tới một tuyến đầu
ra.
Các ma trận sử dụng thường là
ma trận vuông kích thước
(nxn)
Nhận xét:
Trường chuyển mạch không
gian S mang tính thời gian nếu
xét về tính chu kỳ của quá
trình đóng ngắt tiếp ñiểm, tuy
nhiên chu kỳ này là cố ñịnh
cho tất cả các cuộc nối qua
trường chuyển mạch. Nhược
điểm luôn tồn tại trong các
trường chuyển mạch không
gian S là khả năng tắc nghẽn
khi có nhiều hơn một yêu cầu
chuyển mạch TS đầu vào cùng
muốn ra một cổng đầu ra.
Một ma trận chuyển mạch
không tắc nghẽn hoàn toàn
được ñịnh nghĩa là một ma trận
có khả năng đáp ứng được các
kết nối từ các đầu vào bất kỳ
tới các đầu ra bất kỳ. Hiện
tượng tranh chấp cổng đầu ra
trong nội bộ trường chuyển
mạch được gọi là hiện tượng
tắc nghẽn nội. Để giải quyết
vấn đề trên, các trường chuyển

ngăn nhớ: n; dung lượng ngăn
nhớ: 8 bit). Như vậy, bộ nhớ
SMEM lưu toàn bộ thông tin
trong một khung tín hiệu
PCM để đảm bảo tốc độ
luồng thông tin qua trường
chuyển mạch, tốc độ ghi đọc
của CMEM phải lớn gấp 2
lần tốc độ luồng trên tuyến
PCM đầu vào hoặc đầu ra.
Khối điều khiển khu vực gồm
một số khối như: Bộ nhớ điều
khiển CMEM lưu trữ các
thông tin điều khiển SMEM, số
thứ tự của ngăn nhớ và nội
dung dữ liệu trong CMEM thể
hiện các chỉ số khe thời gian
TS cần trao đổi nội dung tin.
TS.C nhận tín hiệu từ đồng
hồ hệ thống để điều khiển các
bộ chọn SEL1, SEL2 nhằm
đồng bộ hoá quá trình ghi đọc
thông tin dữ liệu cho CMEM
và SMEM.
Nguyên tắc hoạt động:
Quá trình ghi các tín hiệu chứa
trong các khe thời gian đầu vào
của tầng chuyển mạch T vào S-
MEM được thực hiện lần lượt
theo bộ đếm khe thời gian.

từ trung tâm xử lí CC. Để thực
hiện điều này CC sẽ thực hiện
nạp số liệu về địa chỉ nhị phân
ô nhớ số “x” của S-MEM vào
ô nhớ số “y” của C-MEM. Sau
đó CC giao quyền điều khiển
cục bộ cho chuyển mạch tầng
T trực tiếp thực hiện quá trình
trao đổi khe thời gian theo yêu
cầu chuyển mạch.
Quá trình tiếp diễn theo từng
chu kì 125 micro giây.
Dung lượng chuyển mạch T
tăng dẫn đến tần số ghi/đọc bộ
nhớ cũng phải tăng, nên yêu
cầu thời gian truy nhập bộ nhớ
nhanh hơn.
Chuyển mạch T với n TS
tương ứng với chuyển mạch
nxn, chu kì tín hiệu PCM 125
micro giây và dùng mã 8 bit
nhị phân, dung lượng chuyển
mạch T(n) như sau:
T-Switch Capacity (n) = 125
micro giõy x P(bit)/8 x A x t
Trong đó:
P : Số bit song song được trao
đổi đồng thời (nói chung là 8
bits)
A: Thời gian truy nhập trung

phối ghép giữa chuyển mạch S
và T. Sự phối ghép khác nhau
dẫn đến các trường chuyển
mạch có tính chất khác nhau,
đồng thời chẳng những nó làm
tăng dung lượng hệ thống mà
còn làm giảm giá thành thiết
bị.
Khối chuyển mạch số cấu trúc
TST cấu tạo từ 3 tầng chuyển
mạch T1, S và T2 kết nối với
nhau như hình vẽ.
Điều khiển trường chuyển
mạch TST kiểu đối ngẫu (A*)
và bộ nhớ dùng chung (B*)
Cấu trúc chức năng:
Tầng chuyển mạch thời gian
T1 phía đầu vào kết nối khe
thời gian vào với một khe thời
gian rỗi nào đó trong đường
Bus dẫn tới đầu vào của trường
chuyển mạch không gian S.
Trong khi đó, tầng chuyển
mạch thời gian T2 phía đầu ra
kết nối khe thời gian đã được
chọn từ chuyển mạch tầng S
tới khe thời gian ra theo yêu
cầu. Như vậy cuộc gọi được
kết nối qua tầng chuyển mạch
có thể được định tuyến qua

SMEM 1(T1) – S – SMEM N
(T2), các bộ nhớ CMEM 1
(T1) và CMEM N (T2) có nội
dung tương ứng 15(5) và
15(10).
Hướng kết nối từ B-A qua
SMEM N (T1) – S – SMEM 1
(T2), các bộ nhớ CMEM
N(T1) và CMEM 1 (T2) có nội
dung tương ứng 15(10) và
15(5).
Từ nội dung các khối điều
khiển chuyển mạch T như trên
hình vẽ, ta nhận thấy hai khối
điều khiển CMEM 1(T1) và
CMEM 1(T2) hoàn toàn giống
nhau, cũng như vậy đối với
CMEM N (T1) và CMEM N
(T2).
Để tiết kiệm số bộ điều khiển
ta có thể sử dụng 01 bộ điều
khiển sử dụng điều khiển
chung cho 2 bộ điều khiển. Vì
trường hợp đang xét là trường
hợp đặc biệt khi ta chọn khe
thời gian trung gian giống nhau
(TS15), điều này sẽ không
đúng với trường hợp tổng quát
khi A và B cùng được kết nối
tới cùng một khối chuyển

Trong kĩ thuật chuyển mạch
gói, nội dung thông tin được
truyền được mang trong các
gói có độ dài cố định hoặc
thay đổi, tùy theo từng
phương pháp cắt mảnh tạo
gói. Ví dụ, một trạm có bản
tin muốn gửi qua mạng
chuyển mạch gói, nhưng độ
dài bản tin lớn hơn so với độ
dài cực đại thì nó phải phân
chia bản tin thành nhiều gói
và các gói được gửi lần lượt
lên mạng. Để quản trị được
luồng gói này có 2 phương
thức chuyển các gói từ nguồn
tới đích.
Mô hình mạng chuyển mạch
gói
Đó là phương pháp biểu đồ
(Datagram) và mạch ảo
(Virtual Circuit)
Trong phương pháp Datagram,
mỗi gói được truyền độc lập
với các gói khác, không liên
quan gì đến các gói đã được
truyền trước đó. Giả thiết là
trạm A trong hình có 3 bản tin
1,2,3 cần gửi đến E. Nó truyền
tất cả các gói đến nút 2 và 4.

mạch kênh – được gọi là mạch
ảo. Trong mỗi gói, ngoài phần
số liệu thực còn có thêm chỉ thị
liên kết kênh ảo được sử dụng
để định tuyến cho việc chuyển
gói đi.
Ưu điểm của Datagram là
không có pha thiết lập, do vậy
khi trạm gửi số liệu ngắn thì
Datagram sẽ phân phát nhanh
hơn. Datagram mềm dẻo hơn
vì khi một phần của mạng có
sự cố thì nó sẽ tự định tuyến lại
để tránh tắc nghẽn. Kiểu này
chỉ có 1 pha chuyển thông tin.
Ưu điểm của chuyển mạch ảo
là tuyến được thiết lậpcho tất
cả các gói, độ hữu dụng của
các gói cao hơn, kiểu này phù
hợp cho chuyển các bản tin
dài. Kiểu này gồm 3 pha là
thiết lập, chuyển thông tin và
giải phóng.
Câu 8: Cấu trúc bộ định
tuyến qua các thế hệ?
Thế hệ thứ I:
Kiến trúc bộ định tuyến thế hệ
I
K ª n h l o g i c K ª n h ¶ o K ª n h l o g i c
M ¹ n g c h u y Ó n m ¹ c h g ã i