LỜI NÓI ĐẦU
Từ xa xưa nhu cầu trao đổi thông tin của con người đã được hình thành. Khi đó, nhận
thức của con người chưa cao nên chỉ sử dụng những ám hiệu, kí hiệu hết sức giản đơn để
trao đổi thông tin với nhau.
Theo thời gian, nhiều công trình khoa học ra đời, chất lượng cuộc sống của con người
ngày càng được hoàn thiện. Do đó, nhu cầu trao đổi thông tin cũng tăng lên. Yêu cầu về
việc trao đổi thông tin giữa con người cách xa hàng nghìn cây số được đặt ra.
Với sự phát triển của khoa học và công nghệ, nhu cầu trên của con người đã được giải
quyết. Mạng viễn thông ra đời đã đáp ứng được hầu hết những nhu cầu đó của con người.
Việc truyền thoại, số liệu đã trở nên rất giản đơn.
Kỹ thuật chuyển mạch là một trong những kỹ thuật mấu chốt trong các mạng truyền
thông. Sự phát triển mạnh mẽ của hạ tầng truyền thông trong một số năm gần đây đã làm
cho kỹ thuật chuyển mạch có những bước tiến nhảy vọt.
Trong đề tài này, nhóm chúng em nghiên cứu về vấn đề “ Chiến lược sử dụng bộ đệm và
các kỹ thuật định tuyến trong chuyển mạch gói”. Trong suốt thời gian tìm hiểu đề tài,
chúng em xin gửi lời cảm ơn tới các thầy, cô giáo trong trường và đặc biệt là cô giáo
Nguyễn Thị Ngân đã giúp đỡ chúng em hoàn thành đề tài.
Trong quá trình tìm hiểu không thể tránh những thiếu sót, vì vậy rất mong nhận được sự
góp ý của thầy cô và các bạn .
Chúng em xin chân thành cám ơn.
NHÓM 5

MỤC LỤC
CHIẾN LƯỢC SỬ DỤNG BỘ ĐỆM VÀ KỸ THUẬT ĐỊNH
TUYẾN TRONG CHUYỂN MẠCH GÓI
I. Chiến lược sử dụng bộ đệm
1. Giới thiệu chung
Như chúng ta đã biết trong chuyển mạch gói nút chuyển mạch là sự kết
hợp của một cơ cấu chuyển mạch, bộ xử lý mào đầu gói đồng thời thực
hiện chức năng xếp hàng và chuyển mạch phân chia theo không gian.
Mỗi gói tin gồm phần mào đầu và phần tải trọng sẽ được mang đi từ một

a) Chuyển mạch đệm đầu vào
Các trường chuyển mạch đệm đầu vào gồm một ma trận không gian bố
trí các bộ đệm tại tất cả các cổng vào để giải quyết vấn đề tranh chấp.
Mô hình chuyển mạch đệm đầu vào được mô tả như hình dưới đây:

Hình 1.Chuyển mạch đệm đầu vào
Cấu trúc trường chuyển mạch bao gồm 3 khối chính:
 Bộ đệm đầu vào FIFO
 Khối ma trận chuyển mạch
 Khối giải quyết tranh chấp
Các gói tin đi tới trường chuyển mạch được lưu giữ tại các bộ đệm đầu
vào chờ khi đầu ra rỗi. khối ma trận chuyển mạch thực hiện chức năng
định tuyến nội bộ , có thể được cấu tạo từ các ma trận crossbar. Khối giải
quyết tranh chấp có chức năng xác định địa chỉ của các cổng đầu vào và
đầu ra tương ứng, thực hiện phân bổ chúng.
Một ưu điểm quan trọng của chuyển mạch hàng đợi đầu vào là chuyển
mạch tốc độ cao có thể thực hiện dễ dàng, bởi vì chuyển mạch hàng đợi
đầu vào có tốc độ hoạt động bộ đệm mong muốn, cân bằng và xấp xỉ tốc
độ cổng. Vì vậy, chuyển mạch với cơ chế đệm đầu vào có thể tăng kích
thước dễ dàng.
Tuy nhiên, chuyển mạch đệm đầu vào phải đối mặt với độ thông qua bị
hạn chế bởi hiện tượng nghẽn đầu dòng HOL(Head Of Line) và vấn đề
sắp xếp các gói tin để tránh tranh chấp tại đầu ra của trường chuyển
mạch không gian. Vấn đề đầu tiên có thể được giả quyết thông qua việc
tăng tốc độ điều khiển trường chuyển mạch hoặc mở rộng các liên kết
trung gian. Vấn đề chống tranh chấp cổng đầu ra sẽ được thực hiện qua
các lược đồ điều khiển, một lược đồ điều khiển thông dụng nhất đã được
đề xuất bởi HUI qua thuật toán chiếm cổng 3 giai đoạn. Ngoài ra còn
một số lược đồ dựa trên kiểu quay vòng các khoảng thời gian chiếm cổng
và phương pháp chiếm cổng đầu ra ảo.

chiếm. Sau đó gói tin được chuyển qua trường chuyển mạch theo đường
cổng đã chiếm.
Nhược điểm:
Nhược điểm chủ yếu của thuật toán này nằm tại 2 pha đầu khi xử lý tiêu
đề. Quá trình gửi thông tin chiếm cổng và xác nhận cổng sẽ làm trễ quá
trình xử lý gói tin trong trường chuyển mạch, nhất là khi trường chuyển
mạch được yêu cầu xử lý tốc độ cao. Các yếu tố phụ thuộc vào tốc độ xử
lý nằm tại kích thước của trường chuyển mạch và kích thước của trường
thông tin. Với giả thiết ma trận chuyển mạch có kích thước ( 1000x1000)
và các gói cố độ dài 1000 bit, tiêu đề chiếm khoảng 14%. Điều này ngụ ý
rằng trường chuyển mạch phải hoạt động ít nhất tại tốc độ 170Mbps để xử
lý các luồng 150Mbps.
 Thuật toán giải quyết tranh chấp dựa trên kiểu nghịch vòng
Thuật toán mạch vòng không cần chức năng phân loại, sự phối hợp giữa
các bộ đệm đầu vào được thực hiện trên 2 chu kỳ phục vụ:
- Thứ nhất cho nghẽn đầu ra qua kích hoạt các bộ điều khiển đệm.
- Thứ hai là chỉ định các đầu ra không thể phục vụ tới các bộ điều khiển
đệm còn lại.
Cơ chế nghịch vòng là cơ chế phân chia thời gian logic theo chu kỳ chọn
cổng chuyển mạch. Trong lược đồ này các bộ điều khiển cổng đầu vào
được liên đấu nối thành thành cấu trúc mạch vòng. Một token được tạo ra
tuần tự tương ứng tới tất cả các cổng đầu ra. Token được chiếm khi nó tới
tại cổng đầu tiên chứa đầu ra liên kết với token. Đầu vào nào chiếm token
đầu tiên thì sẽ được phép chuyển gói tin tới cổng đầu ra tương ứng. Ma
trận chuyển mạch không cần đẩy tốc độ lên mà vẫn thực hiện được nhiệm
vụ chuyển mạch.
Nhược điểm:
+ Tốc độ bit tăng lên trong mạch vòng với kích thước của chuyển mạch.
+ Không đảm bảo sự công bằng tại quá trình chiếm token.
 Các cấu trúc giải quyết tranh chấp khác

cho cả nhóm kênh khi được chỉ định trên cùng một tuyến truyền dẫn trong
cùng một thời gian. Độ thông qua có thể đạt được trong trường hợp này là
90% trong trường hợp nhóm kênh là 32. Với cùng một kích thước nhóm
kênh và cửa sổ, độ thông qua trong trường hợp này đơn giản hơn so với
lược đồ cửa sổ.
b) Chuyển mạch đệm đầu ra
Được thực hiện bởi một ma trận chuyển mạch không gian đầu vào và
mỗi đầu ra chuyển mạch được trang bị một bộ đệm FIFO. Các gói tin
cùng tranh chấp tại một đầu ra sẽ được lưu trữ tạm thời vào trong các bộ
đệm này
Cấu trúc mô tả như trong hình 2.

Hình 2. Chuyển mạch đệm đầu ra
Ưu điểm :
- Vì các chuyển mạch hàng đợi đầu ra không bị nghẽn dòng tiêu đề HOL nên
hiệu năng của trường chuyển mạch này tốt hơn so với chuyển mạch đệm đầu
vào. Độ thông qua của chuyển mạch đệm đầu ra đạt 81%.
Nhược điểm :
- Dung lượng trường chuyển mạch bị giới hạn bởi bộ nhớ. Giả sử, khi tất cả N
gói tin đầu vào đều cùng ra trên một cổng đầu ra, lúc này bộ đệm không thể
lưu N gói tin trong cùng một khe thời gian nếu trường chuyển mạch có kích
thước lớn và tốc độ đầu vào quá cao. Việc thiếu bộ nhớ sẽ gây tắc nghẽn cục
bộ tại đầu ra và các gói sẽ bị tổn thất trong khi các bộ nhớ khác có thể còn
trống mà không được sử dụng.
Thông thường, các cổng đầu ra ngoài bộ đệm FIFO còn có them bộ lọc địa
chỉ AF. Bộ lọc AF có chức năng xác định địa chỉ của các cổng đầu vào và lọc
các địa chỉ có đầu ra tương ứng trên cổng đầu ra. Các bộ lọc AF và các bộ
đệm FIFO hoạt động độc lập và có thể thiết kế riêng biệt nhằm tăng hiệu quả
xử lí gói tin.
c) Chuyển mạch đệm trung tâm

bất kỳ có thể chiếm toàn bộ không gian nhớ trong một khoảng thời gian. Đó
chính là hiện tượng Hogging. Để giải quyết vấn đề này có thể có mọt phương
án khác nhằm phân hoạch vùng nhớ thành các cùng nhỏ hơn độc lập. Tuy
nhiên, phương pháp phân hoạch thành các vùng nhớ nhỏ hơn sẽ gây nên tổn
thất khi một số lưu lượng chiếm một đường nào đó lớn trong khi các đương
khác không có hoặc rất ít lưu lượng, điều này cũng làm giảm hiệu năng tổng
thể của mạng chuyển mạch khi việc sử dụng bộ nhớ đệm không hiệu quả.
II. Kỹ thuật định tuyến trong chuyển mạch gói
Định tuyến là một quá trình lựa chọn con đường cho gói tin truyền qua mạng.
Định tuyến được xem như là khả năng của node trong vấn đề lựa chọn đường
dẫn cho thông tin qua mạng. Định tuyến là một khái niệm cốt lõi của chuyển
mạch gói và nhiều loại mạng khác nhau. Định tuyến cung cấp phương tiện tìm
kiếm các tuyến đường theo các thông tin mà gói tin truyền trên mạng.
Mỗi node trong mạng nhận gói dữ liệu từ một đường vào rồi chuyển tiếp tới một
đường ra hướng đến đích của dữ liệu. Như vậy mỗi node trung gian phải thực
hiện chức năng chọn đường hay còn gọi là định tuyến.
Mục tiêu cơ bản của các phương pháp định tuyến nhằm sử dụng tối đa tài
nguyên mạng và tối thiểu gia thành mạng. Để đạt được điều này kỹ thuật định
tuyến phải tối ưu được các tham số mạng và người sử dụng như : xác suất tắc
nghẽn, độ trễ, độ tin cậy, giá thành… Vì vậy một kỹ thuật định tuyến phải thực
hiện tốt 2 chức năng sau :
- Quyết định chọn đường theo những tiêu chuẩn tối ưu nào đó.
- Cập nhật thông tin định tuyến, tức là thông tin dùng cho chức năng.
Tùy thuộc và kiến trúc hạ tần, cơ sở mạng mà các kỹ thuật định tuyến khác nhau
được áp dụng. Các tiêu chuẩn tối ưu khi chọn đường từ trạm nguồn tới trạm đích
có thể phụ thuộc và yêu cầu người sử dụng dịch vụ mạng. Giữa mạng và người
sử dụng có thể có các thỏa thuận ràng buộc về chất lượng dịch vụ cung cấp hay
một số yêu cầu khác. Do đó có thể dẫn tới khả năng chọn đường của mạng chỉ là
cận tối ưu đối với một loại hình dịch vụ cụ thể. Chức năng cập nhật thông tin
địch tuyến là chức năng quan trọng nhất mà các giao thức định tuyến phải thừa