Chủ đề: Không gian giá trị sequence number dạng que kẹo (lollipop) trong LSA

Khái niệm có cái tên gợi tính tò mò này được tiến sỹ Radia Perlman đặt cho.

Mô hình sequence number dạng que kẹo – là một kết hợp giữa mô hình đường thẳng và mô hình vòng.

Vấn đề của mô hình dạng vòng là không có số nào nhỏ hơn mọi số khác
Vấn đề của mô hình dạng đường thẳng là chúng không phải dạng vòng, điều đó làm cho bộ chuỗi số của nó bị giới hạn

Khi router A khởi động lại, nó sẽ bắt đầu với một số sequence number nhỏ hơn mọi số khác. Các neighbor sẽ nhận diện giá trị này, và nếu chúng có trong database một giá trị pre-start number là b từ router A, chúng có thể gửi giá trị này tới router A, và router A sẽ nhảy lên giá trị này.
Router A có thể gửi nhiều hơn một LSA trước khi nó nhận đ.c thông tin vế số sequence number mà nó đã sở hữu, trước khi khởi động lại.

Do đó, vấn đề ở đây là cần phải có đủ lượng số restart number để cho A không thể sử dụng hết tất cả chúng, trước khi neighbor thông báo với nó về một giá trị sequence number mà router A trước đó đã sử dụng, hoặc trước khi giá trị sequence number đó hết thời hạn được lưu lại trên mọi database.

Các giá trị restart number này tạo thành phần que của hình que kẹo.
Khi chúng đã được sử dụng, hoặc sau khi một neighbor đã được cấp một giá trị sequence number mà A có thể nhảy, A sẽ vào phần không gian số dạng vòng.

Một trong những mục đích của việc sử dụng không gian địa chỉ dạng thanh kẹo là việc cho phép dùng các số thứ tự đã được sử dụng, trong đó, -k<0<k

Các giá trị số âm sẽ được tiến từ k tới 1, tạo thành phần que.
Và các giá trị số dương sẽ tiến từ 0 tới k, tạo thành phần vòng.

Các luật của Perlman với các số thứ tự được thực hiện như sau:
Cho hai số a và b và một không gian số thứ tự n, b là số “mới được cập nhật” hơn a khi và chỉ khi:
a < 0 và a < b, hoặc
a > 0, a < b, và (b - a) < n/2, or
a > 0, b > 0, a > b, và (a - b) > n/2

Hình dưới đây mô tả một không gian số thứ tự dạng thanh kẹo.



Một vùng không gian số 32 bit được sử dụng, với hai trường số: 2^31 số dương và 2^31 số âm.
Hai giá trị - N (- 2^31, hay 0x80000000) và N - 1 (2^31 + 1, hay 0x7FFFFFFF) sẽ không đ.c sử dụng.
Một router khi có kết nối sẽ bắt đầu từ giá trị sequence number – N + 1, và tiến dần tới 0, khi đó, nó sẽ vào không gian số vòng.
Khi sequence number tiến tới N – 2, giá trị sequence number này lại quay về 0 (một lần nữa, giá trị N – 1 không đ.c sử dụng)

Sau đó, giả sử router được khởi động lại.
Giá trị sequence number của LSA cuối cùng được gửi đi trước khi restart là 0x00005de3 (là một phần của không gian số vòng).
Khi router đồng bộ database với neighbor của nó, sau khi nó được khởi động lại, router sẽ gửi đi LSA với sequence number = 0x80000001 (- N +1)
Router neighbor sẽ nhìn vào database của nó và tìm thấy giá trị pre-start LSA có giá trị sequence number là 0x00005DE3.
Router neighbor gửi LSA này tới router vừa khởi động lại, và báo rằng đây là giá trị trước đó của router.
Router vừa khởi động lại sẽ ghi lại giá trị LSA với sequence number dương.
Nếu sau này nó cần phải gửi một bản copy của LSA , giá trị sequence number sẽ là 0x00005DE6.

Không gian số dạng que kẹo được sử dụng từ những phiên bản OSPF đầu tiên (OSPFv1 – RFC 1131). Version hiện nay của OSPF là OSPFv2 (RFC 1247) tận dụng được những tối đa ưu điểm của không gian số dạng que kẹo.

Đúng như anh netsys nói, không gian sequence number dạng vòng tròn chưa giải quyết được triệt để các vấn để nảy sinh từ không gian số dạng đường thẳng. Mình xin mô tả một chút về không gian số dạng vòng tròn cùng với tình huống lỗi mà nó gây ra ở bài này:

Trong không gian số dạng vòng tròn : các số sequence number bao kín thành vòng tròn, trong một không gian số 32 bit, trong đó – số đằng sau số 4.294.967.295 là 0. Các sự cố vẫn có thể xảy ra trong mô hình này.

Chuỗi số dạng vòng tròn tạo ra một lỗi phi logic như sau: nếu như x là một số bất kỳ nằm giữa 1 và 4.294.967.295 thì xảy ra tình trạng 0 < x < 0 (vì đằng sau 4.294.967.295 lại là 0).

Một internetwork được thiết lập tốt có thể kiểm soát được tình huống này bằng việc đưa vào hai luật để chỉ ra khi nào thì một sequence number lớn hơn một sequence number khác.

Cho một không gian n số và hai số sequence number: a và b, a sẽ là số “mới” hơn b nếu thỏa mãn một trong hai điều kiện sau:
• a > b, và (a – b) ≤ n/2 (1)
• a < b, và (b – a) > n/2 (2)


Để đơn giản hơn, ta xét một ví dụ với không gian số 6 bit được mô tả ở hình dưới đây:


n = 2^6 = 64, => n/2 = 32.

Với hai số là 48 và 18, 48 là số mới hơn 18, vì theo luật (1)
48 > 18 và(48 – 18) = 30, và 30 < 32.

Với hai số là 3 và 48, 3 là số mới hơn 48, vì theo luật (2)
3 < 48 và (48 – 3) = 45 ,và 45 > 32.

Với hai số là 3 và 18, 18 là số mới hơn 3, vì theo luật (1)
18 > 3 và (18 – 3) = 15 ,và 15 < 32.

=> Do đó, hai luật này làm hoàn chỉnh cho chuỗi số vòng tròn



Nhưng còn đối với một internetwork được thiết lập không tốt thì có vấn đề gì xảy ra?

Ta hãy xem xét với một không gian sequence number với 6 bit.Khi một router trong internetwork ngừng hoạt động, nhưng nó đã gửi ra 3 bản tin LSA với giá trị sequence number là 44 (101100). Không may là router neighbor của router này cũng bị lỗi, và nó sẽ drop một số bit. Router neighbor drop 1 bit ở trường sequence number trong LSA thứ hai, và drop thêm 1 bit khác ở trường sequence trong LSA thứ ba, rồi nó truyền đi cả ba LSA. Kết quả là sẽ có ba bản tin LSA với các giá trị sequence number khác nhau:

44 ---- (101100)
40 ---- (101000)
8 ---- (001000)

Áp dụng các luật trên vào, ta thấy rằng 44 mới hơn 40, trong khi 40 lại mới hơn 8, và 8 mới hơn 44. Kết quả là tất cả các LSA sẽ bị gửi ra và thay thế liên tiếp, và database sẽ bị viết đè liên tiếp bởi giá trị LSA mới hơn, cho tới khi bộ nhớ đệm bị đầy vì LSA, CPU sẽ quá tải và toàn bộ internetwork sụp đổ.

Tình huống trên nghe qua có vẻ như khó xảy ra, tuy nhiên thực tế là nó đã từng xảy ra. Mạng ARPANET, tiền thân của Internet hiện đại, đã sử dụng một giao thức định tuyến link-state với không gian số 6 bit dạng vòng tròn. Và vào ngày 27/10/1980, hai router đã bị lỗi, dẫn tới việc toàn bộ mạng ARPANET ngừng hoạt động theo đúng tình huống nêu trên.