Đồ án Giao thức OSPF và các ứng dụng của nó trong mạng IP

(Variable length subnetmask). Hoạt của OSPF được mô tả một cách tổng quát như sau: Các Router OSPF gửi các gói Hello ra tất cả các giao diện chạy OSPF. Nếu hai Router chia sẻ một liên kết dữ liệu cùng chấp nhận các tham số được chỉ ra trong gói Hello, chúng sẽ trở thành các Neighbor của nhau. Adjacency có thể coi như các liên kết ảo điểm - điểm, được hình thành giữa các Neighbor. Việc hình thành một Adjacency phụ thuộc vào các yếu tố như loại Router trao đổi các gói Hello và loại mạng sử dụng để các gói Hello truyền trên đó. Sau khi các Adjacency được hình thành, mỗi Router gửi các LSA (Link State Advertisement) qua các Adjacency. Các LSA mô tả tất cả các liên kết của Router và trạng thái của các liên kết. Mỗi Router nhận một LSA từ một Neighbor, ghi LSA vào cơ sở dữ liệu trạng thái liên kết của nó và gửi bản copy tới tất cả các Neighbor khác của nó. Bằng cách trao đổi các LSA trong một Area, tất cả các Router sẽ xây dựng cơ sở dữ liệu trạng thái liên kết của mình giống với các Router khác. Khi cơ sở dữ liệu hoàn chỉnh, mỗi Router sử dụng giải thuật SPF để tính toán đường đi ngắn nhất (đường đi có cost thấp nhất) tới tất cả các đích đã biết. Sơ đồ này gọi là cây SPF. Mỗi Router xây dựng bảng định tuyến từ cây SPF của nó. 3.2 Một số khái niệm sử dụng trong OSPF 3.2.1 Láng giềng (Neighbor) và mối quan hệ thân mật (Adjacency) Trước khi gửi các LSA, các Router OSPF phải khám phá các Neighbor của nó và thiết lập Adjacency với chúng. Danh sách các Neighbor được ghi trong bảng các Neighbor cùng với các liên kết (hoặc giao diện) nối với mỗi Neighbor và các thông tin cần thiết khác. 3.2.2 Giao thức Hello Giao thức Hello thực hiện các chức năng sau: Dùng để khám phá các Neighbor Dùng để quảng cáo các tham số mà hai Router phải chấp nhận trước khi chúng trở thành các Neighbor của nhau. Đảm bảo thông tin hai chiều giữa các Neighbor. Các gói Hello hoạt động như các Keepalive giữa các Neighbor. Dùng để bầu cử DR và BDR trong mạng Broadcast và Nonbroadcast Multiaccess (NBMA). Các Router OSPF gửi các gói Hello định kỳ ra các giao diện OSPF. Chu kỳ gửi được gọi là Hello Interval và được cấu hình trong cơ sở dữ liệu giao diện. Nếu một Router không nhận được gói Hello từ Neighbor trong một khoảng thời gian gọi là Router Dead Interval, nó sẽ khai báo Neighbor này bị Down. Khi một Router nhận một gói Hello từ một Neighbor, nó sẽ kiểm tra xem các trường Area ID , Authentication, Network Mask, Hello Interval, Router Dead Interval và Option trong gói Hello có phù hợp với các giá trị đã được cấu hình ở giao diện đang nhận hay không. Nếu không phù hợp, gói sẽ bị huỷ và Adjacency không được thiết lập. Nếu tất cả phù hợp, gói Hello được khai báo là hợp lệ. Nếu Router ID của Router gốc đã có trong bảng Neighbor của giao diện nhận, Router Dead Interval được reset. Nếu không, nó ghi Router ID này vào bảng Neighbor. Khi một Router gửi một gói Hello, gói Hello sẽ chứa Router ID của tất cả các Neighbor cần thiết trong liên kết mà gói truyền đi. Nếu một Router nhận được một gói Hello hợp lệ có chứa Router ID của nó, Router này sẽ biết rằng thông tin hai chiều đã được thiết lập. 3.2.3 Các loại mạng OSPF định nghĩa năm loại mạng: Mạng điểm - điểm. Mạng quảng bá. Mạng đa truy nhập không quảng bá. Mạng điểm – đa điểm. Các liên kết ảo. Mạng điểm - điểm: là mạng nối hai Router với nhau. Các Neighbor hợp lệ trong mạng điểm - điểm luôn thiết lập Adjacency. Địa chỉ đích của các gói OSPF trong mạng này luôn là địa chỉ lớp D 224.0.0.5 gọi là AllSPF Routers. Mạng quảng bá: Ví dụ như Ethernet, Token Ring, FDDI. Là mạng có khả năng kết nối nhiều hơn hai thiết bị và các thiết bị này đều có thể nhận các gói gửi từ một thiết bị bất kì trong mạng. Các Router OSPF trong mạng quảng bá sẽ bầu cử DR và BDR. Các gói Hello được phát multicast với địa chỉ đích là 224.0.0.5 ( AllSPF Routers). Ngoài ra các gói xuất phát từ DR và BDR cũng được phát multicast với địa chỉ này. Các Router khác sẽ phát multicast các gói cập nhật và xác nhận trạng thái liên kết với địa chỉ lớp D là: 224.0.0.6 gọi là All DRouters. Mạng NBMA (Nonbroadcast - Multiaccess): ví dụ như X25, Frame relay, ATM. Là mạng có khả năng kết nối nhiều hơn hai Router nhưng không có khả năng Broadcast. Tức là một gói gửi bởi một Router trong mạng không được nhận bởi tất cả các Router khác của mạng. Các Router trong NBMA bầu cử DR và BDR. Các gói OSPF được truyền theo kiểu unicast. Mạng điểm – đa điểm: là trường hợp đặc biệt của NBMA. Nó có thể coi là một tập hợp các kết nối điểm - điểm. Các Router trong mạng không phải bầu cử DR và BDR. Các gói OSPF được truyền theo kiểu multicast. Các liên kết ảo: là một cấu trúc đặc biệt được Router hiểu như là các mạng điểm - điểm không đánh số. Các gói OSPF được phát unicast trên các liên kết ảo. 3.2.4 DR và BDR Các mạng đa truy nhập tồn tại hai vấn đề sau liên quan đến quá trình tràn lụt LSA như sau: Thông tin của một Adjacency giữa các Router sẽ tạo ra nhiều LSA không cần thiết. Nếu một mạng đa truy nhập có n Router thì có thể có n(n-1)/2 Adjacency (Hình 3.1). Mỗi Router sẽ tràn lụt n-1 LSA cho các Neighbor của nó cộng với một LSA cho mạng dẫn đến có n(n-1) + 1 = n2 LSA được tạo ra trong mạng. Hình 3.1 Quá trình tràn lụt có thể gây xung đột. Một Router gửi một LSA tới tất cả các Neighbor của nó. Các Neighbor này lại gửi bản copy của LSA nhận được tới các Neighbor của mình dẫn đến tạo ra nhiều bản copy của LSA trong mạng. Để tránh các vấn đề trên, DR được bầu ra trong mạng đa truy nhập. DR có các nhiệm vụ sau: Mô tả mạng đa truy nhập và các Router gắn vào mạng cho phần còn lại của liên mạng. Quản lý quá trình tràn lụt trong mạng đa truy nhập. Mỗi Router trong mạng thiết lập Adjacency với DR (hình 3.2). Chỉ có DR gửi các LSA tới phần còn lại của liên mạng. Một Router có thể là DR đối với mạng này nhưng không là DR đối với mạng khác. Nói cách khác DR chỉ là một đặc tính của giao diện của Router, không phải toàn bộ Router. Hình 3.2 DR đại diện cho mạng đa truy nhập. Các Router khác chỉ thiết lập Adjacency với DR. Nếu DR bị hỏng, một DR mới phải được bầu ra. Các Adjacency mới phải được thiết lập, các Router phải đồng bộ cơ sở dữ liệu của chúng với DR mới. Trong khi các quá trình này diễn ra, mạng sẽ không khả dụng để truyền gói. Để tránh vấn đề này, BDR được bầu cử. Tất cả các Router thiết lập Adjacency với cả DR và BDR. DR và BDR cũng có thể thiết lập Adjacency với nhau. Nếu DR hỏng, BDR sẽ trở thành DR mới. Tóm lại việc bầu cử diễn ra như sau: Khi một Router OSPF được kích hoạt, nó tìm kiếm các Neighbor của nó và kiểm tra DR và BDR. Nếu DR và BDR đã tồn tại, Router sẽ chấp nhận chúng. Nếu không có BDR, một cuộc bầu cử BDR được tiến hành và Router có Priority cao nhất sẽ trở thành BDR. Nếu có nhiều hơn một Router có cùng Priority cao nhất, Router có Router ID cao nhất sẽ trở thành BDR. Nếu chưa có DR, BDR sẽ trở thành DR và cuộc bầu cử BDR mới lại được thực hiện. Chú ý: Priority có thể ảnh hưởng đến quá trình bầu cử DR và BDR nhưng không ảnh hưởng đến các DR và BDR đã được bầu cử. Nếu có một Router có Priority cao hơn các DR và BDR đã được kích hoạt, nó cũng không thể thay thế các DR và BDR này. 3.3 Giao diện OSPF 3.3.1 Cấu trúc dữ liệu giao diện Các thành phần của cấu trúc số liệu giao diện bao gồm: Địa chỉ IP và mặt nạ: là địa chỉ và mặt nạ được cấu hình cho giao diện. Area ID: là Area chứa giao diện. Process ID: dùng để phân biệt các tiến trình OSPF chạy trên một Router. Router ID: dùng để nhận dạng Router Network type: là loại của mạng nối với giao diện. Cost: là cost của các gói đi ra từ giao diện. Cost là một Metric OSPF, được diễn tả bởi 16 bit nguyên không dấu có giá trị từ 1 đến 65535. Inf Trans Delay: là số giây các LSA ra khỏi giao diện với tuổi bị tăng lên. State: là trạng thái chức năng của giao diện được trình bày ở phần sau. Router Priority: 8 bit nguyên không dấu này có giá trị từ 0 đến 255 dùng để bầu cử DR và BDR. DR: là DR của mạng mà giao diện gắn vào. DR này được ghi bởi Router ID của nó và địa chỉ của giao diện gắn vào mạng của DR. BDR: là BDR của mạng mà giao diện gắn vào. BDR này được ghi bởi Router ID của nó và địa chỉ của giao diện gắn vào mạng của BDR. Hello Interval: là khoảng thời gian tính theo giây giữa các lần truyền các gói Hello trên giao diện. Router Dead Interval: là khoảng thời gian tính theo giây mà Router sẽ chờ để nghe các gói Hello từ một Neighbor trước khi nó coi rằng Neighbor này bị Down. Wait Time: là khoảng thời gian Router sẽ chờ DR và BDR được quảng cáo trong gói tin Hello trước khi bắt đầu lựa chọn DR và BDR. Chu kì Wait Time bằng Router Dead Interval. Rxm Interval: là khoảng thời gian tính theo giây Router sẽ chờ giữa các lần truyền lại của các gói OSPF chưa được xác nhận. Hello Timer: Là bộ định thời được lập bằng Hello Interval. Khi nó hết hiệu lực, gói Hello được truyền lại từ giao diện. Neighboring Routers: Danh sách tất cả các Neighbor hợp lệ (có gói Hello được nhìn thấy trong thời gian Router Dead Interval). Autype: Mô tả loại nhận thực sử dụng trong mạng. Autype có thể là Null (không nhận thực), Simple Password, hoặc Cryptographic (Mesage digest). Authentication Key: Nếu chế độ nhận thực là Simple password, Au key là 64 bit. Nếu chế độ nhận thực là Cryptographic, Au key là Message digest. Chế độ Cryptographic cho phép cấu hình nhiều khoá trên một giao diện. 3.3.2 Các trạng thái giao diện Một giao diện OSPF sẽ chuyển đổi qua một số trạng thái khác nhau trước khi nó đủ khả năng làm việc. Các trạng thái đó bao gồm: Down, Point to Point, Waiting, DR, Backup, DRother, và loopback. Hình 3.3 Sự chuyển đổi giữa các trạng thái giao diện OSPF Biến cố vào Ý nghĩa các biến cố IE1 IE2 IE3 IE4 IE5 IE6 IE7 IE8 IE9 IE10 Các giao thức mức thấp chỉ báo rằng giao diện mạng đã sẵn sàng hoạt động. Các giao thức mức thấp chỉ báo rằng giao diện mạng chưa sẵn sàng hoạt động. Ngưòi quản lý mạng hoặc các giao thức mức thấp hơn chỉ ra rằng giao diện được loop up. Người quản lý mạng hoặc các giao thức mức thấp hơn chỉ ra rằng giao diện được loop down. Gói Hello nhận được chỉ ra rằng Neighbor gốc (Neighbor gửi gói Hello này) muốn trở thành DR hoặc BDR và trong mạng chưa có BDR. Wait timer đã hết hiệu lực. Router được bầu cử là DR trong mạng này. Router được bầu cử là BDR trong mạng này. Router không được bầu cử là DR hoặc BDR trong mạng này. Một thay đổi xảy ra trong tập các Neighbor hợp lệ của mạng. Thay đổi này có thể là: Thiết lập kết nối hai chiều với một Neighbor. Mất kết nối hai chiều với một Neighbor. Nhận một gói Hello chỉ ra rằng Neighbor gốc muốn trở thành DR hoặc BDR. Nhận được gói Hello từ DR chỉ ra rằng Router này không muốn làm DR nữa. Nhận được gói Hello từ BDR chỉ ra rằng Router này không muốn làm BDR nữa. Thời gian Router Dead Interval kết thúc mà không nhận được gói Hello từ DR hoặc BDR. Down: Đây là trạng thái giao diện đầu tiên. Ở trạng thái này giao diện không làm việc. Tất cả các tham số của giao diện được lập bằng giá trị ban đầu và không có lưu lượng được truyền hoặc nhận trên giao diện. Point to Point: Trạng thái này chỉ thích hợp với các giao diện kết nối tới các mạng Point to Point, Point to Multipoint và Virtual Link. Khi giao diện ở trạng thái này, nó đã đủ khả năng làm việc. Nó sẽ bắt đầu gửi các gói Hello và thiết lập Adjacency với Neighbor. Waiting: Trạng thái này chỉ thích hợp với các giao diện nối tới các mạng Broadcast và NBMA. Khi chuyển sang trạng thái này, nó bắt đầu gửi và nhận các gói Hello và lập Wait timer. Router sẽ cố gắng xác định DR và BDR trong trạng thái này. DR: Ở trạng thái này, Router là DR và sẽ thiết lập Adjacency với các Router khác trong mạng đa truy nhập. Backup: Ở trạng thái này, Router là BDR và sẽ thiết lập Adjacency với các Router khác. DRother: Ở trạng thái này, Router không là DR hay BDR. Nó sẽ thiết lập Adjacency với chỉ DR và BDR trong khi vẫn theo dõi tất cả các Neighbor khác trong mạng. Loopback: Ở trạng thái này, giao diện được loopback bằng phần mềm hoặc phần cứng. Mặc dù các gói không thể truyền, địa chỉ giao diện vẫn được quảng cáo trong Router LSA để các gói kiểm tra có thể tìm đường tới giao diện. 3.4 Neighbor OSPF 3.4.1 Cấu trúc dữ liệu Neighbor Các thành phần của cấu trúc dữ liệu Neighbor là: Neighbor ID: là Router ID của Neighbor. Neighbor IP address: là địa chỉ IP của giao diện nối tới mạng của Neighbor. Khi một gói OSPF được truyền unicast tới Neighbor, địa chỉ này sẽ là địa chỉ đích. Area ID: Để hai Router trở thành các Neighbor của nhau, Area ID trong gói Hello nhận được phải phù hợp với Area ID của giao diện nhận. Interface: là giao diện gắn vào mạng chứa Neighbor. Neighbor Priority: là Router Priority của Neighbor được chỉ ra trong gói Hello. State: là trạng thái chức năng của Neighbor sẽ được trình bày ở phần sau. Poll Interval: Giá trị này chỉ sử dụng đối với các Neighbor trong mạng NBMA. Vì các Neighbor không thể được tự động khám phá trong mạng NBMA nếu các Neighbor này ở trạng thái Down, do vậy gói Hello sẽ được gửi tới các Neighbor sau mỗi khoảng thời gian nhất định. Khoảng thời gian này gọi là Poll Interval. Neighbor Options: là các khả năng OSPF tuỳ chọn được hỗ trợ bởi Neighbor. Các tuỳ chọn này được trình bày ở phần sau. Inactivity Timer: là Timer có chu kỳ là Router Dead Interval. Timer được reset khi nhận được gói Hello từ Neighbor. Nếu Inactivity Timer hết hiệu lực mà chưa nhận được gói Hello, Neighbor sẽ được khai báo là Down. Designated Router: Địa chỉ này chứa trong trường DR của gói Hello. Backup Designated Router: Địa chỉ này chứa trong trường BDR của gói Hello. Master/Slave: Quan hệ chủ-tớ (được thoả thuận trong trạng thái Exstart) thiết lập Neighbor nào sẽ điều khiển việc đồng bộ cơ sở dữ liệu. DD Sequence Number: là số trình tự của gói Database Description (DD) đang được gửi tới Neighbor. Last Received Database Description Packet: Các bít Initialize, More, Master, các Option và số trình tự của gói DD nhận được cuối cùng được ghi trong cơ sở dữ liệu Neighbor. Thông tin này dùng để xác định xem gói DD tiếp theo có phải là bản sao của gói trước. Link State Retransmission List: là danh sách các LSA đã được tràn lụt trên Adjacency nhưng chưa được công nhận. Các LSA sẽ được truyền lại sau khoảng thời gian RxmtInterval cho đến khi chúng được công nhận hoặc Adjacency bị phá vỡ. Database Summary List: Là danh sách các LSA được gửi tới Neighbor trong gói DD trong quá trình đồng bộ cơ sở dữ liệu. Các LSA tạo nên cơ sở dữ liệu trạng thái liên kết khi Router chuyển sang trạng thái Exchange. Link State Request List: Là danh sách các LSA trong cá gói DD của Neighbor “mới” hơn các LSA trong cơ sở dữ liệu trạng thái liên kết. Các gói yêu cầu trạng thái liên kết được gửi tới Neighbor yêu cầu các bản copy của các LSA này. Khi nhận được các LSA yêu cầu trong các gói cập nhật trạng thái liên kết, danh sách yêu cầu trạng thái liên kết sẽ được rút dần cho đến hết. 3.4.2 Các trạng thái Neighbor Một Router sẽ chuyển Neighbor qua một số trạng thái trước khi Neighbor được coi là Full Adjacency. Các trạng thái đó bao gồm: Down, Attemt, Init, 2-Way, Extart, Exchange, Loading, và Full. Down: là trạng thái đầu tiên của Neighbor khi cuộc hội thoại (giữa Router và Neighbor) chỉ ra rằng không có gói Hello nào được gửi từ Neighbor trong Router Dead Interval cuối cùng. Các gói Hello không được gửi tới Neighbor bị Down trừ trường hợp các Neighbor này thuộc mạng NBMA. Trong trường hợp này, các gói Hello được gửi theo chu kỳ Poll Interval. Nếu Neighbor chuyển xuống trạng thái Down từ trạng thái cao hơn thì danh sách truyền lại trạng thái liên kết, mô tả cơ sở dữ liệu, và yêu cầu trạng thái liên kết bị xoá bỏ. Attempt: Trạng thái này chỉ ứng dụng cho các Neighbor trong mạng NBMA, ở đây các Neighbor được cấu hình bằng tay. Một Router (đủ khả năng để trở thành DR) sẽ chuyển một Neighbor sang trạng thái Attempt khi giao diện nối tới Neighbor được kích hoạt đầu tiên hoặc khi Router là DR hoặc BDR. Một Router sẽ gửi các gói tới một Neighbor ở trạng thái Attempt theo chu kỳ HelloInterval thay vì PollInterval. Hình 3.4 Sự chuyển đổi trạng thái từ Down sang Full Init: Trạng thái này chỉ ra rằng đã nhận được gói Hello từ Neighbor trong Router Dead Interval cuối cùng nhưng kết nối hai chiều chưa được thiết lập. Router sẽ chứa Router ID của tất cả các Neighbor ở trạng thái này hoặc trạng thái cao hơn trong trường Neighbor của gói Hello. 2-Way: Trạng thái này chỉ ra rằng Router đã “nhìn thấy“ Router ID của nó trong trường Neighbor của gói Hello mà Neighbor gửi tới. Điều này có nghĩa là kết nối hai chiều đã được thiết lập. Trong mạng đa truy nhập, Neighbor phải ở trạng thái này hoặc cao hơn để có thể được chọn là DR hoặc BDR. Việc nhận một gói DD từ một Neighbor ở trạng thái Init sẽ chuyển Neighbor này sang trạng thái 2-Way. ExStart: Ở trạng thái này, Router và các Neighbor của nó thiết lập quan hệ Masterr/Slave và xác định số trình tự DD đầu tiên để chuẩn bị cho việc trao đổi các gói DD. Neighbor có địa chỉ giao diện cao nhất sẽ là Master. Exchange: Router gửi các gói DD mô tả toàn bộ cơ sở dữ liệu trạng thái liên kết của nó tới các Neighbor đang ở trạng thái Exchange. Router cũng gửi các gói yêu cầu trạng thái liên kết tới các Neighbor ở trạng thái này để yêu cầu các LSA mới nhất. Loading: Router sẽ gửi các gói yêu cầu trạng thái liên kết tới các Neighbor ở trạng thái này để yêu cầu các LSA mới hơn đã được chỉ ra ở trạng thái Exchange nhưng chưa nhận được. Full: Neighbor ở trạng thái này là Adjacent hoàn toàn và các Adjacency sẽ xuất hiện trong các Router LSA và Network LSA. Hình 3.5 Sự chuyển đổi trạng thái từ Init sang Full Biến cố vào Ý nghĩa IE1 IE2 IE3 IE4 IE5 IE6 IE7 IE8 IE9 IE10 IE11 IE12 IE13 IE14 IE15 IE16 Chỉ xảy ra đối với các Neighbor kết nối với mạng NBMA. IE1 xảy ra bởi một trong các điều kiện sau: Giao diện nối tới mạng NBMA được kích hoạt đầu tiên, và Neighbor đủ điều kiện tham gia bầu cử DR. Router là DR hoặc BDR, và Neighbor không đủ điều kiện tham gia bầu cử để trở thành DR. Một gói Hello hợp lệ được nhận từ Neighbor. Neighbor không thể liên lạc được nữa. Router nhận nhìn thấy Router ID của nó đầu tiên trong gói Hello của Neighbor hoặc nhận được gói DD từ Neighbor. Neighbor không thể thiết lập Adjacency. Xảy ra bởi một trong các điều kiện sau: Trạng thái Neighbor chuyển trước tiên sang trạng thái 2-way. Trạng thái giao diện thay đổi. Adjacency sẽ được hình thành với Neighbor này. Quan hệ chủ tớ được thiết lập và số trình tự DD được trao đổi. Việc trao đổi các gói DD được hoàn thành. Các khoản mục còn tồn tại trong danh sách yêu cầu trạng thái liên kết. Danh sách yêu cầu trạng thái liên kết rỗng. Adjacency sẽ được phá vỡ và được reset lại. IE12 xảy ra bởi một trong các điều kiện sau: Nhận được gói DD có số trình tự DD không đúng. Nhận được gói DD có trường Option khác với trường Option của gói DD cuối cùng. Nhận được gói DD khác ngoài gói đầu tiên có bit Init được lập. Nhận được gói yêu cầu một LSA không có trong cơ sở dữ liệu. Nhận được một gói Hello từ Neighbor trong đó Router ID của Router nhận không có trong trường Neighbor. Xảy ra khi trạng thai giao diện thay đổi. Adjacency với Neighbor này sẽ tiếp tục tồn tại hay tiếp tục hình thành. Adjacency với Neighbor này sẽ không tiếp tục tồn tại hay không tiếp tục hình thành. Quyết định Ý nghĩa DP1 DP2 DP3 Một Adjacency sẽ được thiết lập với Neighbor hay không? Một Adjacency sẽ được hình thành nếu một trong các điều kiện sau xảy ra: Loại mạng là Point to Point. Loại mạng là Point to Multipoint. Loại mạng là liên kết ảo. Router là DR trong mạng của Neighbor. Router là BDR trong mạng của Neighbor. Neighbor là DR. Neighbor là BDR. Danh sách yêu cầu trạng thái liên kết đối với Neighbor này rỗng không? Adjacency với Neighbor có tiếp tục tồn tại hay không? 3.5 Thiết lập mối quan hệ thân mật (Adjacency) Các Neighbor trong các mạng Point to Point, Point to Multipoint, và liên kết ảo luôn thiết lập Adjacency với nhau trừ phi các tham số trong các gói Hello của chúng không phù hợp. Trong các mạng quảng bá và NBMA, DR và BDR sẽ thiết lập Adjacency với tất cả các Neighbor còn các DRother sẽ không thiết lập Adjacency với các DRother khác. Quá trình xây dựng Adjacency sử dụng ba loại gói OSPF sau: Gói mô tả cơ sở dữ liệu DD (loại 2). Gói yêu cầu trạng thái liên kết (loại 3). Gói cập nhật trạng thái liên kết (loại 4). Gói DD đặc biệt quan trọng trong quá trình xây dựng Adjacency. Các gói DD sẽ chứa Header của các LSA trong cơ sở dữ liệu trạng thái liên kết của Router gốc. Router nhận sẽ nhận các gói DD và kiểm tra các Header này để quyết định xem liệu nó đã có bản copy mới nhất của LSA trong cơ sở dữ liệu của nó. Ngoài ra gói DD còn chứa ba cờ được sử dụng để quản lí quá trình xây dựng Adjacency. Ba cờ đó là: Bit I (Initial bit): I = 1 chỉ ra rằng gói DD đầu tiên gửi. Bit M (More bit): M = 1 chỉ ra rằng đây không phải gói DD cuối cùng được gửi. Bit MS (Master/Slave bit): MS = 1 chỉ ra rằng gói DD được gửi từ Router là Master. Khi cuộc đàm phán Master/Slave bắt đầu ở trạng thái Exstart, cả hai Neighbor sẽ cùng yêu cầu trở thành Master bằng cách gửi một gói DD rỗng với bit MS = 1. Neighbor có Router ID thấp hơn sẽ là Slave và truyền trở lại gói DD có MS = 0 và số trình tự DD được lập theo số trình tự của Master. Gói DD này sẽ là gói DD đầu tiên chứa các bản tóm tắt LSA. Khi cuộc đàm phán Master/Slave hoàn thành, trạng thái Neighbor sẽ chuyển sang Exchange. Ở trạng thái Exchange, các Neighbor sẽ tiến hành đồng bộ cơ sở dữ liệu của chúng. Danh sách tóm tắt cơ sở dữ liệu được ghi cùng với các Header của tất cả các LSA trong cơ sở dữ liệu của Router. Các gói DD chứa danh sách các Header của các LSA được gửi tới Neighbor. Nếu một Router thấy rằng Neighbor của nó có một LSA không có trong cơ sở dữ liệu của nó, hoặc rằng Neighbor có bản copy của một LSA (đã biết) mới hơn, nó đặt LSA này vào danh sách yêu cầu trạng thái liên kết. Sau đó nó gửi gói yêu cầu trạng thái liên kết để yêu cầu bản copy của LSA này. Các gói cập nhật trạng thái liên kết vận chuyển các LSA được yêu cầu. Khi nhận được các LSA yêu cầu, Router sẽ xoá Header của các LSA nhận được khỏi danh sách yêu cầu trạng thái liên kết. Tất cả các LSA gửi đi trong gói cập nhật trạng thái liên kết phải được xác nhận. Do vậy, các LSA đã được truyền được ghi vào danh sách truyền lại trạng thái liên kết. Khi một LSA được xác nhận, nó sẽ được xoá khỏi danh sách này. LSA có thể được xác nhận theo hai cách: Xác nhận rõ ràng: Khi nhận được gói xác nhận trạng thái liên kết chứa LSA Header. Xác nhận ngầm: Khi nhận được gói cập nhật trạng thái liên kết chứa phiên bản LSA giống với phiên bản đã gửi. (Cả hai LSA đều mới hơn các LSA khác). Master điều khiển quá trình đồng bộ và đảm bảo chỉ có gói DD được truyền đi vào thời điểm đó. Khi Slave nhận một gói DD từ Master, Slave xác nhận việc này bằng cách gửi một gói DD có cùng số trình tự tới Master. Nếu Master không nhận được xác nhận của gói này trong khoảng thời gian RxmtInterval, nó sẽ gửi tiếp bản copy của gói đó đến Slave. Slave gửi các gói DD chỉ để đáp lại các gói DD mà nó nhận từ Master. Nếu gói DD nhận được có số trình tự mới, Slave gửi gói DD có cùng số trình tự với gói này. Nếu số trình tự của gói nhận được giống với gói xác nhận trước đó, gói xác nhận được truyền lại. Khi quá trình đồng bộ hoàn tất, một trong hai sự chuyển đổi trạng thái sau sẽ xảy ra: Nếu vẫn còn các mục trong danh sách yêu cầu trạng thái liên kết, Router sẽ chuyển trạng thái của Neighbor sang trạng thái Loading. Nếu danh sách yêu cầu trạng thái là rỗng, Router sẽ chuyển trạng thái của Neighbor sang trạng thái Full. Master biết rằng quá trình đồng bộ đã hoàn tất khi nó gửi tất cả các gói DD cần thiết để diễn tả đầy đủ cơ sở dữ liệu trạng thái liên kết của nó tới Slave và nhận được gói DD với bit M = 0. Slave biết rằng quá trình đồng bộ đã hoàn tất khi nó nhận được gói DD có bit M = 0 và gửi một gói DD xác nhận có bit M = 0. Hình dưới đây chỉ ra ví dụ về một quá trình đồng bộ cơ sở dữ liệu cùng với sự chuyển đổi trạng thái Neighbor. Hình 3.6 Ví dụ một quá trình đồng bộ cơ sở dữ liệu Quá trình đồng bộ cơ sở dữ liệu ở hình trên gồm các bước sau: RT1 được kích hoạt trong mạng đa truy nhập và gửi một gói Hello. Do nó chưa biết được về một Neighbor nào, nên trường Neighbor của gói là rỗng, trường DR và BDR được lập bằng 0.0.0.0. RT2 nhận được gói Hello từ RT1, nó tạo một cấu trúc dữ liệu Neighbor cho RT1 và chuyển trạng thái của RT1 thành Init. RT2 gửi một gói Hello chứa Router ID của RT1 trong trường Neighbor và địa chỉ giao diện của nó trong trường DR. Khi nhận được gói Hello từ RT2, RT1 sẽ biết được Router ID của mình. RT1 tạo một cấu trúc dữ liệu Neighbor cho RT2 và chuyển trạng thái của RT2 sang trạng thái Exstart để chuẩn bị cho việc đàm phán Master/Slave. Sau đó nó tạo một gói DD rỗng (không chứa các Header của các LSA) có số trình tự là x, bit I = 1 (chỉ ra rằng đây là gói DD đầu tiên của RT1), bit M = 1 ( chỉ ra rằng đây không phải là gói DD cuối cùng), bit MS = 1 (chỉ ra rằng RT1 muốn là Master). RT2 chuyển trạng thái của RT1 sang trạng thái Exstart tron