Debian Codegraph @

rfc1105.html

raw
1 <pre>Network Working Group K. Lougheed
2 Request for Comments: 1105 cisco Systems
3 Y. Rekhter
4 T.J. Watson Research Center, IBM Corp.
5 June 1989
6
7 <span class="h1">A Border Gateway Protocol (BGP)</span>
8
9 Status of this Memo
10
11 This RFC outlines a specific approach for the exchange of network
12 reachability information between Autonomous Systems.
13
14 At the time of this writing, the Border Gateway Protocol
15 implementations exist for cisco routers as well as for the NSFNET
16 Nodal Switching Systems. A public domain version for "gated" is
17 currently being implemented.
18
19 Distribution of this memo is unlimited.
20
21 <span class="h2"><a class="selflink" id="section-1" href="#section-1">1</a>. Introduction</span>
22
23 The Border Gateway Protocol (BGP) is an inter-autonomous system
24 routing protocol. It is built on experience gained with EGP as
25 defined in <a href="./rfc904">RFC 904</a> [<a href="#ref-1" title="&quot;Exterior Gateway Protocol Formal Specification&quot;">1</a>] and EGP usage in the NSFNET Backbone as
26 described in <a href="./rfc1092">RFC 1092</a> [<a href="#ref-2" title="&quot;EGP and Policy Based Routing in the New NSFNET Backbone&quot;">2</a>] and <a href="./rfc1093">RFC 1093</a> [<a href="#ref-3" title="&quot;The NSFNET Routing Architecture&quot;">3</a>].
27
28 The primary function of a BGP speaking system is to exchange network
29 reachability information with other BGP systems. This network
30 reachability information includes information on the autonomous
31 systems (AS's) that traffic must transit to reach these networks.
32 This information is sufficient to construct a graph of AS
33 connectivity from which routing loops may be pruned and policy
34 decisions at an AS level may be enforced.
35
36 BGP runs over a reliable transport level protocol. This eliminates
37 the need to implement explicit update fragmentation, retransmission,
38 acknowledgement, and sequencing. Any authentication scheme used by
39 the transport protocol may be used in addition to BGP's own
40 authentication mechanisms.
41
42 The initial BGP implementation is based on TCP [<a href="#ref-4" title="&quot;Transmission Control Protocol - DARPA Internet Program Protocol Specification&quot;">4</a>], however any
43 reliable transport may be used. A message passing protocol such as
44 VMTP [<a href="#ref-5" title="&quot;VMTP: Versatile Message Transaction Protocol&quot;">5</a>] might be more natural for BGP. TCP will be used, however,
45 since it is present in virtually all commercial routers and hosts.
46 In the following descriptions the phrase "transport protocol
47 connection" can be understood to refer to a TCP connection. BGP uses
48 TCP port 179 for establishing its connections.
49
50
51
52 <span class="grey">Lougheed &amp; Rekhter [Page 1]</span></pre>
53 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-2" ></span>
54 <span class="grey"><a href="./rfc1105">RFC 1105</a> BGP June 1989</span>
55
56
57 <span class="h2"><a class="selflink" id="section-2" href="#section-2">2</a>. Summary of Operation</span>
58
59 Two hosts form a transport protocol connection between one another.
60 They exchange messages to open and confirm the connection parameters.
61 The initial data flow is the entire BGP routing table. Incremental
62 updates are sent as the routing tables change. Keepalive messages
63 are sent periodically to ensure the liveness of the connection.
64 Notification messages are sent in response to errors or special
65 conditions. If a connection encounters an error condition, a
66 notification message is sent and the connection is optionally closed.
67
68 The hosts executing the Border Gateway Protocol need not be routers.
69 A non-routing host could exchange routing information with routers
70 via EGP or even an interior routing protocol. That non-routing host
71 could then use BGP to exchange routing information with a border
72 gateway in another autonomous system. The implications and
73 applications of this architecture are for further study.
74
75 If a particular AS has more than one BGP gateway, then all these
76 gateways should have a consistent view of routing. A consistent view
77 of the interior routes of the autonomous system is provided by the
78 intra-AS routing protocol. A consistent view of the routes exterior
79 to the AS may be provided in a variety of ways. One way is to use
80 the BGP protocol to exchange routing information between the BGP
81 gateways within a single AS. In this case, in order to maintain
82 consist routing information, these gateways MUST have direct BGP
83 sessions with each other (the BGP sessions should form a complete
84 graph). Note that this requirement does not imply that all BGP
85 gateways within a single AS must have direct links to each other;
86 other methods may be used to ensure consistent routing information.
87
88 <span class="h2"><a class="selflink" id="section-3" href="#section-3">3</a>. Message Formats</span>
89
90 This section describes message formats and actions to be taken when
91 errors are detected while processing these messages.
92
93 Messages are sent over a reliable transport protocol connection. A
94 message is processed after it is entirely received. The maximum
95 message size is 1024 bytes. All implementations are required to
96 support this maximum message size. The smallest message that may be
97 sent consists of a BGP header without a data portion, or 8 bytes.
98
99 The phrase "the BGP connection is closed" means that the transport
100 protocol connection has been closed and that all resources for that
101 BGP connection have been deallocated. Routing table entries
102 associated with the remote peer are marked as invalid. This
103 information is passed to other BGP peers before being deleted from
104 the system.
105
106
107
108 <span class="grey">Lougheed &amp; Rekhter [Page 2]</span></pre>
109 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-3" ></span>
110 <span class="grey"><a href="./rfc1105">RFC 1105</a> BGP June 1989</span>
111
112
113 <span class="h3"><a class="selflink" id="section-3.1" href="#section-3.1">3.1</a> Message Header Format</span>
114
115 Each message has a fixed size header. There may or may not be a data
116 portion following the header, depending on the message type. The
117 layout of these fields is shown below.
118
119 0 1 2 3
120 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
121 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
122 | Marker | Length |
123 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
124 | Version | Type | Hold Time |
125 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
126
127 Marker: 16 bits
128
129 The Marker field is 16 bits of all ones. This field is used to
130 mark the start of a message. If the first two bytes of a message
131 are not all ones then we have a synchronization error and the BGP
132 connection should be closed after sending a notification message
133 with opcode 5 (connection not synchronized). No notification data
134 is sent.
135
136 Length: 16 bits
137
138 The Length field is 16 bits. It is the total length of the
139 message, incluluding header, in bytes. If an illegal length is
140 encountered (more than 1024 bytes or less than 8 bytes), a
141 notification message with opcode 6 (bad message length) and two
142 data bytes of the bad length should be sent and the BGP connection
143 closed.
144
145 Version: 8 bits
146
147 The Version field is 8 bits of protocol version number. The
148 current BGP version number is 1. If a bad version number is
149 found, a notification message with opcode 8 (bad version number)
150 should be sent and the BGP connection closed. The bad version
151 number should be included in one byte of notification data.
152
153 Type: 8 bits
154
155 The Type field is 8 bits of message type code. The following type
156 codes are defined:
157
158
159
160
161
162
163
164 <span class="grey">Lougheed &amp; Rekhter [Page 3]</span></pre>
165 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-4" ></span>
166 <span class="grey"><a href="./rfc1105">RFC 1105</a> BGP June 1989</span>
167
168
169 1 - OPEN
170 2 - UPDATE
171 3 - NOTIFICATION
172 4 - KEEPALIVE
173 5 - OPEN CONFIRM
174
175 If an unrecognized type value is found, a notification message
176 with opcode 7 (bad type code) and data consisting of the byte of
177 type field in question should be sent and the BGP connection
178 closed.
179
180 Hold Timer: 16 bits.
181
182 This field contains the number of seconds that may elapse since
183 receiving a BGP KEEPALIVE or BGP UPDATE message from our BGP peer
184 before we declare an error and close the BGP connection.
185
186 <span class="h3"><a class="selflink" id="section-3.2" href="#section-3.2">3.2</a> OPEN Message Format</span>
187
188 After a transport protocol connection is established, the first
189 message sent by either side is an OPEN message. If the OPEN message
190 is acceptable, an OPEN CONFIRM message confirming the OPEN is sent
191 back. Once the OPEN is confirmed, UPDATE, KEEPALIVE, and
192 NOTIFICATION messages may be exchanged.
193
194 In addition to the fixed size BGP header, the OPEN message contains
195 the following fields.
196
197 0 1 2 3
198 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
199 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
200 | My Autonomous System | Link Type | Auth. Code |
201 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
202 | |
203 | Authentication Data |
204 | |
205 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
206
207 My Autonomous System: 16 bits
208
209 This field is our 16 bit autonomous system number. If there is a
210 problem with this field, a notification message with opcode 9
211 (invalid AS field) should be sent and the BGP connection closed.
212 No notification data is sent.
213
214 Link Type: 8 bits
215
216 The Link Type field is a single octet containing one of the
217
218
219
220 <span class="grey">Lougheed &amp; Rekhter [Page 4]</span></pre>
221 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-5" ></span>
222 <span class="grey"><a href="./rfc1105">RFC 1105</a> BGP June 1989</span>
223
224
225 following codes defining our position in the AS graph relative to
226 our peer.
227
228 0 - INTERNAL
229 1 - UP
230 2 - DOWN
231 3 - H-LINK
232
233 UP indicates the peer is higher in the AS hierarchy, DOWN
234 indicates lower, and H-LINK indicates at the same level. INTERNAL
235 indicates that the peer is another BGP speaking host in our
236 autonomous system. INTERNAL links are used to keep AS routing
237 information consistent with an AS with multiple border gateways.
238 If the Link Type field is unacceptable, a notification message
239 with opcode 1 (link type error in open) and data consisting of the
240 expected link type should be sent and the BGP connection closed.
241 The acceptable values for the Link Type fields of two BGP peers
242 are discussed below.
243
244 Authentication Code: 8 bits
245
246 The Authentication Code field is an octet whose value describes
247 the authentication mechanism being used. A value of zero
248 indicates no BGP authentication. Note that a separate
249 authentication mechanism may be used in establishing the transport
250 level connection. If the authentication code is not recognized, a
251 notification message with opcode 2 (unknown authentication code)
252 and no data is sent and the BGP connection is closed.
253
254 Authentication Data: variable length
255
256 The Authentication Data field is a variable length field
257 containing authentication data. If the value of Authentication
258 Code field is zero, the Authentication Data field has zero length.
259 If authentication fails, a notification message with opcode 3
260 (authentication failure) and no data is sent and the BGP
261 connection is closed.
262
263 <span class="h3"><a class="selflink" id="section-3.3" href="#section-3.3">3.3</a> OPEN CONFIRM Message Format</span>
264
265 An OPEN CONFIRM message is sent after receiving an OPEN message.
266 This completes the BGP connection setup. UPDATE, NOTIFICATION, and
267 KEEPALIVE messages may now be exchanged.
268
269 An OPEN CONFIRM message consists of a BGP header with an OPEN CONFIRM
270 type code. There is no data in an OPEN CONFIRM message.
271
272
273
274
275
276 <span class="grey">Lougheed &amp; Rekhter [Page 5]</span></pre>
277 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-6" ></span>
278 <span class="grey"><a href="./rfc1105">RFC 1105</a> BGP June 1989</span>
279
280
281 <span class="h3"><a class="selflink" id="section-3.4" href="#section-3.4">3.4</a> UPDATE Message Format</span>
282
283 UPDATE messages are used to transfer routing information between BGP
284 peers. The information in the UPDATE packet can be used to construct
285 a graph describing the relationships of the various autonomous
286 systems. By applying rules to be discussed, routing information
287 loops and some other anomalies may be detected and removed from the
288 inter-AS routing.
289
290 Whenever an error in a UPDATE message is detected, a notification
291 message is sent with opcode 4 (bad update), a two byte subcode
292 describing the nature of the problem, and a data field consisting of
293 as much of the UPDATE message data portion as possible. UPDATE
294 messages have the following format:
295
296 0 1 2 3
297 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
298 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
299 | Gateway |
300 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
301 | AS count | Direction | AS Number |
302 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
303 | repeat (Direction, AS Number) pairs AS count times |
304 / /
305 / /
306 | |
307 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
308 | Net Count |
309 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
310 | Network |
311 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
312 | Metric | |
313 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +
314 | repeat (Network, Metric) pairs Net Count times |
315 / /
316 / /
317 | |
318 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
319
320 Gateway: 32 bits.
321
322 The Gateway field is the address of a gateway that has routes to
323 the Internet networks listed in the rest of the UPDATE message.
324 This gateway MUST belong to the same AS as the BGP peer who
325 advertises it. If there is a problem with the gateway field, a
326 notification message with subcode 6 (invalid gateway field) is
327 sent.
328
329
330
331
332 <span class="grey">Lougheed &amp; Rekhter [Page 6]</span></pre>
333 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-7" ></span>
334 <span class="grey"><a href="./rfc1105">RFC 1105</a> BGP June 1989</span>
335
336
337 AS count: 8 bits.
338
339 This field is the count of Direction and AS Number pairs in this
340 UPDATE message. If an incorrect AS count field is detected,
341 subcode 1 (invalid AS count) is specified in the notification
342 message.
343
344 Direction: 8 bits
345
346 The Direction field is an octet containing the direction taken by
347 the routing information when exiting the AS defined by the
348 succeeding AS Number field. The following values are defined.
349
350 1 - UP (went up a link in the graph)
351 2 - DOWN (went down a link in the graph)
352 3 - H_LINK (horizontal link in the graph)
353 4 - EGP_LINK (EGP derived information)
354 5 - INCOMPLETE (incomplete information)
355
356 There is a special provision to pass exterior learned (non-BGP)
357 routes over BGP. If an EGP learned route is passed over BGP, then
358 the Direction field is set to EGP-LINK and the AS Number field is
359 set to the AS number of the EGP peer that advertised this route.
360 All other exterior-learned routes (non-BGP and non-EGP) may be
361 passed by setting AS Number field to zero and Direction field to
362 INCOMPLETE. If the direction code is not recognized, a
363 notification message with subcode 2 (invalid direction code) is
364 sent.
365
366 AS Number: 16 bits
367
368 This field is the AS number that transmitted the routing
369 information. If there is a problem with this AS number, a
370 notification message with subcode 3 (invalid autonomous system) is
371 sent.
372
373 Net Count: 16 bits.
374
375 The Net Count field is the number of Metric and Network field
376 pairs which follow this field. If there is a problem with this
377 field, a notification with subcode 7 (invalid net count field) is
378 sent.
379
380 Network: 32 bits
381
382 The Network field is four bytes of Internet network number. If
383 there is a problem with the network field, a notification message
384 with subcode 8 (invalid network field) is sent.
385
386
387
388 <span class="grey">Lougheed &amp; Rekhter [Page 7]</span></pre>
389 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-8" ></span>
390 <span class="grey"><a href="./rfc1105">RFC 1105</a> BGP June 1989</span>
391
392
393 Metric: 16 bits
394
395 The Metric field is 16 bits of an unspecified metric. BGP metrics
396 are comparable ONLY if routes have exactly the same AS path. A
397 metric of all ones indicates the network is unreachable. In all
398 other cases the metric field is MEANINGLESS and MUST BE IGNORED.
399 There are no illegal metric values.
400
401 <span class="h3"><a class="selflink" id="section-3.5" href="#section-3.5">3.5</a> NOTIFICATION Message Format</span>
402
403 NOTIFICATION messages are sent when an error condition is detected.
404 The BGP connection is closed shortly after sending the notification
405 message.
406
407 0 1 2 3
408 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
409 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
410 | Opcode | Data |
411 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +
412 | |
413 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
414
415 Opcode: 16 bits
416
417 The Opcode field describes the type of NOTIFICATION. The
418 following opcodes have been defined.
419
420 1 (*) - link type error in open. Data is one byte of proper
421 link type.
422 2 (*) - unknown authentication code. No data.
423 3 (*) - authentication failure. No data.
424 4 - update error. See below for data description.
425 5 (*) - connection out of sync. No data.
426 6 (*) - invalid message length. Data is two bytes of
427 bad length.
428 7 (*) - invalid message type. Data is one byte of bad
429 message type.
430 8 (*) - invalid version number. Data is one byte of
431 bad version.
432 9 (*) - invalid AS field in OPEN. No data.
433 10 (*) - BGP Cease. No data.
434
435 The starred opcodes in the list above are considered fatal errors
436 and cause transport connection termination.
437
438 The update error (opcode 4) has as data 16 bits of subcode
439 followed by the last UPDATE message in question. After the
440 subcode comes as much of the data portion of the UPDATE in
441
442
443
444 <span class="grey">Lougheed &amp; Rekhter [Page 8]</span></pre>
445 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-9" ></span>
446 <span class="grey"><a href="./rfc1105">RFC 1105</a> BGP June 1989</span>
447
448
449 question as possible. The following subcodes are defined:
450
451 1 - invalid AS count
452 2 - invalid direction code
453 3 - invalid autonomous system
454 4 - EGP_LINK or INCOMPLETE_LINK link type at other than
455 the end of the AS path list
456 5 - routing loop
457 6 - invalid gateway field
458 7 - invalid Net Count field
459 8 - invalid network field
460
461 Data: variable
462
463 The Data field contains zero or more bytes of data to be used in
464 diagnosing the reason for the NOTIFICATION. The contents of the
465 Data field depend upon the opcode. See the opcode descriptions
466 above for more details.
467
468 <span class="h3"><a class="selflink" id="section-3.6" href="#section-3.6">3.6</a> KEEPALIVE Message Format</span>
469
470 BGP does not use any transport protocol based keepalive mechanism to
471 determine if peers are reachable. Instead KEEPALIVE messages are
472 exchanged between peers often enough as not to cause the hold time
473 (as advertised in the BGP header) to expire. A reasonable minimum
474 frequency of KEEPALIVE exchange would be one third of the Hold Time
475 interval.
476
477 As soon as the Hold Time associated with BGP peer has expired, the
478 BGP connection is closed and BGP deallocates all resources associated
479 with this peer.
480
481 The KEEPALIVE message is a BGP header without any data.
482
483 <span class="h2"><a class="selflink" id="section-4" href="#section-4">4</a>. BGP Finite State machine.</span>
484
485 This section specifies BGP operation in terms of a Finite State
486 Machine (FSM). Following is a brief summary and overview of BGP
487 operations by state as determined by this FSM. A condensed version
488 of the BGP FSM is found in Appendix 1.
489
490 Initially BGP is in the BGP_Idle state.
491
492 BGP_Idle state:
493
494 In this state BGP refuses all incoming BGP connections. No
495 resources are allocated to the BGP neighbor. In response to the
496 Start event (initiated by either system or operator) the local
497
498
499
500 <span class="grey">Lougheed &amp; Rekhter [Page 9]</span></pre>
501 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-10" ></span>
502 <span class="grey"><a href="./rfc1105">RFC 1105</a> BGP June 1989</span>
503
504
505 system initializes all BGP resources and changes its state to
506 BGP_Active.
507
508 BGP_Active state:
509
510 In this state BGP is trying to acquire a BGP neighbor by opening a
511 transport protocol connection. If the transport protocol open
512 fails (for example, retransmission timeout), BGP stays in the
513 BGP_Active state.
514
515 Otherwise, the local system sends an OPEN message to its peer,
516 and changes its state to BGP_OpenSent. Since the hold time of the
517 peer is still undetermined, the hold time is initialized to some
518 large value.
519
520 In response to the Stop event (initiated by either system or
521 operator) the local system releases all BGP resources and changes
522 its state to BGP_Idle.
523
524 BGP_OpenSent state:
525
526 In this state BGP waits for an OPEN message from its peer. When
527 an OPEN message is received, all fields are checked for
528 correctness. If the initial BGP header checking detects an error,
529 BGP deallocates all resources associated with this peer and
530 returns to the BGP_Active state. Otherwise, the Link Type,
531 Authentication Code, and Authentication Data fields are checked
532 for correctness.
533
534 If the link type is incorrect, a NOTIFICATION message with opcode
535 1 (link type error in open) is sent. The following combination of
536 link type fields are correct; all other combinations are invalid.
537
538 Our view Peer view
539 UP DOWN
540 DOWN UP
541 INTERNAL INTERNAL
542 H-LINK H-LINK
543
544 If the link between two peers is INTERNAL, then AS number of both
545 peers must be the same. Otherwise, a NOTIFICATION message with
546 opcode 1 (link type error in open) is sent.
547
548 If both peers have the same AS number and the link type between
549 these peers is not INTERNAL, then a NOTIFICATION message with
550 opcode 1 (link type error in open) is sent.
551
552 If the value of the Authentication Code field is zero, any
553
554
555
556 <span class="grey">Lougheed &amp; Rekhter [Page 10]</span></pre>
557 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-11" ></span>
558 <span class="grey"><a href="./rfc1105">RFC 1105</a> BGP June 1989</span>
559
560
561 information in the Authentication Data field (if present) is
562 ignored. If the Authentication Code field is non-zero it is
563 checked for known authentication codes. If authentication code is
564 unknown, then the BGP NOTIFICATION message with opcode 2 (unknown
565 authentication code) is sent.
566
567 If the Authentication Code value is non-zero, then the
568 corresponding authentication procedure is invoked. The default
569 values are a zero Authentication Code and no Authentication Data.
570
571 If any of the above tests detect an error, the local system closes
572 the BGP connection and changes its state to BGP_Idle.
573
574 If there are no errors in the BGP OPEN message, BGP sends an OPEN
575 CONFIRM message and goes into the BGP_OpenConfirm state. At this
576 point the hold timer which was originally set to some arbitrary
577 large value (see above) is replaced with the value indicated in
578 the OPEN message.
579
580 If disconnect notification is received from the underlying
581 transport protocol or if the hold time expires, the local system
582 closes the BGP connection and changes its state to BGP_Idle.
583
584 BGP_OpenConfirm state:
585
586 In this state BGP waits for an OPEN CONFIRM message. As soon as
587 this message is received, BGP changes its state to
588 BGP_Established. If the hold timer expires before an OPEN CONFIRM
589 message is received, the local system closes the BGP connection
590 and changes its state to BGP_Idle.
591
592 BGP_Established state:
593
594 In the BGP_Established state BGP can exchange UPDATE,
595 NOTIFICATION, and KEEPALIVE messages with its peer.
596
597 If disconnect notification is received from the underlying
598 transport protocol or if the hold time expires, the local system
599 closes the BGP connection and changes its state to BGP_Idle.
600
601 In response to the Stop event initiated by either the system or
602 operator, the local system sends a NOTIFICATION message with
603 opcode 10 (BGP Cease), closes the BGP connection, and changes its
604 state to BGP_Idle.
605
606
607
608
609
610
611
612 <span class="grey">Lougheed &amp; Rekhter [Page 11]</span></pre>
613 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-12" ></span>
614 <span class="grey"><a href="./rfc1105">RFC 1105</a> BGP June 1989</span>
615
616
617 <span class="h2"><a class="selflink" id="section-5" href="#section-5">5</a>. UPDATE Message Handling</span>
618
619 A BGP UPDATE message may be received only in the BGP_Established
620 state. When a BGP UPDATE message is received, each field is checked
621 for validity. When a NOTIFICATION message is sent regarding an
622 UPDATE, the opcode is always 4 (update error), the subcode depends on
623 the type of error, and the rest of the data field is as much as
624 possible of the data portion of the UPDATE that caused the error.
625
626 If the Gateway field is incorrect, a BGP NOTIFICATION message is sent
627 with subcode 6 (invalid gateway field). All information in this
628 UPDATE message is discarded.
629
630 If the AS Count field is less than or equal to zero, a BGP
631 NOTIFICATION is sent with subcode 1 (invalid AS count). Otherwise,
632 the complete AS path is extracted and checked as described below.
633
634 If one of the Direction fields in the AS route list is not defined, a
635 BGP NOTIFICATION message is with subcode 2 (invalid direction code).
636
637 If one of the AS Number fields in the AS route list is incorrect, a
638 BGP NOTIFICATION message is sent with subcode 3 (invalid autonomous
639 system).
640
641 If either a EGP_LINK or a INCOMPLETE_LINK link type occurs at other
642 than the end of the AS path, a BGP NOTIFICATION message is sent with
643 subcode 4 (EGP_LINK or INCOMPLETE_LINK link type at other than the
644 end of the AS path list).
645
646 If none of the above tests failed, the full AS route is checked for
647 AS loops.
648
649 AS loop detection is done by scanning the full AS route and checking
650 that each AS in this route occurs only once. If an AS loop is
651 detected, a BGP NOTIFICATION message is sent with subcode 5 (routing
652 loop).
653
654 If any of the above errors are detected, no further processing is
655 done. Otherwise, the complete AS path is correct and the rest of the
656 UPDATE message is processed.
657
658 If the Net Count field is incorrect, a BGP NOTIFICATION message is
659 sent with subcode 7 (invalid Net Count field).
660
661 Each network and metric pair listed in the BGP UPDATE message is
662 checked for a valid network number. If the Network field is
663 incorrect, a BGP Notification message is sent with subcode 8 (invalid
664 network field). No checking is done on the metric field. It is up
665
666
667
668 <span class="grey">Lougheed &amp; Rekhter [Page 12]</span></pre>
669 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-13" ></span>
670 <span class="grey"><a href="./rfc1105">RFC 1105</a> BGP June 1989</span>
671
672
673 to a particular implementation to decide whether to continue
674 processing or terminate it upon the first incorrect network.
675
676 If the network, its complete AS path, and the gateway are correct,
677 then the route is compared with other routes to the same network. If
678 the new route is better than the current one, then it is flooded to
679 other BGP peers as follows:
680
681 - If the BGP UPDATE was received over the INTERNAL link, it is not
682 propagated over any other INTERNAL link. This restriction is
683 due to the fact that all BGP gateways within a single AS
684 form a completely connected graph (see above).
685
686 - Before sending a BGP UPDATE message over the non-INTERNAL links,
687 check the AS path to insure that doing so would not cause a
688 routing loop. The BGP UPDATE message is then propagated (subject
689 to the local policy restrictions) over any of the non-INTERNAL
690 link of a routing loop would not result.
691
692 - If the BGP UPDATE message is propagated over a non-INTERNAL link,
693 then the current AS number and link type of the link over which
694 it is going to be propagated is prepended to the full AS path
695 and the AS count field is incremented by 1. If the BGP UPDATE
696 message is propagated over an INTERNAL link, then the full AS
697 path passed unmodified and the AS count stays the same. The
698 Gateway field is replaced with the sender's own address.
699
700 <span class="h2"><a class="selflink" id="section-6" href="#section-6">6</a>. Acknowledgements</span>
701
702 We would like to express our thanks to Len Bosack (cisco Systems),
703 Jeff Honig (Cornell University) and all members of the IWG task force
704 for their contributions to this document.
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724 <span class="grey">Lougheed &amp; Rekhter [Page 13]</span></pre>
725 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-14" ></span>
726 <span class="grey"><a href="./rfc1105">RFC 1105</a> BGP June 1989</span>
727
728
729 Appendix 1
730
731 BGP FSM State Transitions and Actions.
732
733 This Appendix discusses the transitions between states in the BGP FSM
734 in response to BGP events. The following is the list of these states
735 and events.
736
737 BGP States:
738
739 1 - BGP_Idle
740 2 - BGP_Active
741 3 - BGP_OpenSent
742 4 - BGP_OpenConfirm
743 5 - BGP_Established
744
745 BGP Events:
746
747 1 - BGP Start
748 2 - BGP Transport connection open
749 3 - BGP Transport connection closed
750 4 - BGP Transport connection open failed
751 5 - Receive OPEN message
752 6 - Receive OPEN CONFIRM message
753 7 - Receive KEEPALIVE message
754 8 - Receive UPDATE messages
755 9 - Receive NOTIFICATION message
756 10 - Holdtime timer expired
757 11 - KeepAlive timer expired
758 12 - Receive CEASE message
759 13 - BGP Stop
760
761 The following table describes the state transitions of the BGP FSM
762 and the actions triggered by these transitions.
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780 <span class="grey">Lougheed &amp; Rekhter [Page 14]</span></pre>
781 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-15" ></span>
782 <span class="grey"><a href="./rfc1105">RFC 1105</a> BGP June 1989</span>
783
784
785 Event Actions Message Sent Next State
786 --------------------------------------------------------------------
787 BGP_Idle (1)
788 1 Initialize resources none 2
789 BGP_Active (2)
790 2 Initialize resources OPEN 3
791 4 none none 2
792 13 Release resources none 1
793
794 BGP_OpenSent(3)
795 3 none none 1
796 5 Process OPEN is OK OPEN CONFIRM 4
797 Process OPEN Message failed NOTIFICATION 1
798 11 Restart KeepAlive timer KEEPALIVE 3
799 13 Release resources none 1
800
801 BGP_OpenConfirm (4)
802 6 Complete initialization none 5
803 3 none none 1
804 10 Close transport connection none 1
805 11 Restart KeepAlive timer KEEPALIVE 4
806 13 Release resources none 1
807
808 BGP_Established (5)
809 7 Process KEEPALIVE none 5
810 8 Process UPDATE is OK UPDATE 5
811 Process UPDATE failed NOTIFICATION 5
812 9 Process NOTIFICATION none 5
813 10 Close transport connection none 1
814 11 Restart KeepAlive timer KEEPALIVE 5
815 12 Close transport connection NOTIFICATION 1
816 13 Release resources none 1
817 --------------------------------------------------------------------
818
819 All other state-event combinations are considered fatal errors and
820 cause the termination of the BGP transport connection (if necessary)
821 and a transition to the BGP_Idle state.
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836 <span class="grey">Lougheed &amp; Rekhter [Page 15]</span></pre>
837 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-16" ></span>
838 <span class="grey"><a href="./rfc1105">RFC 1105</a> BGP June 1989</span>
839
840
841 The following is a condensed version of the above state transition
842 table.
843
844 Events|BGP_Idle BGP_Active BGP_OpenSent BGP_OpenConfirm BGP_Estab
845 | (1) | (2) | (3) | (4) | (5)
846 |-------------------------------------------------------------
847 1 | 2 | | | |
848 | | | | |
849 2 | | 3 | | |
850 | | | | |
851 3 | | | 1 | 1 |
852 | | | | |
853 4 | | 2 | | |
854 | | | | |
855 5 | | | 4 or 1 | |
856 | | | | |
857 6 | | | | 5 |
858 | | | | |
859 7 | | | | | 5
860 | | | | |
861 8 | | | | | 5
862 | | | | |
863 9 | | | | | 5
864 | | | | |
865 10 | | | | 1 | 1
866 | | | | |
867 11 | | | 3 | 4 | 5
868 | | | | |
869 12 | | | | | 1
870 | | | | |
871 13 | | 1 | 1 | 1 | 1
872 | | | | |
873 --------------------------------------------------------------
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892 <span class="grey">Lougheed &amp; Rekhter [Page 16]</span></pre>
893 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-17" ></span>
894 <span class="grey"><a href="./rfc1105">RFC 1105</a> BGP June 1989</span>
895
896
897 References
898
899 [<a id="ref-1">1</a>] Mills, D., "Exterior Gateway Protocol Formal Specification", <a href="./rfc904">RFC</a>
900 <a href="./rfc904">904</a>, BBN, April 1984.
901
902 [<a id="ref-2">2</a>] Rekhter, Y., "EGP and Policy Based Routing in the New NSFNET
903 Backbone", <a href="./rfc1092">RFC 1092</a>, T. J. Watson Research Center, February 1989.
904
905 [<a id="ref-3">3</a>] Braun, H-W., "The NSFNET Routing Architecture", <a href="./rfc1093">RFC 1093</a>,
906 MERIT/NSFNET Project, February 1989.
907
908 [<a id="ref-4">4</a>] Postel, J., "Transmission Control Protocol - DARPA Internet
909 Program Protocol Specification", <a href="./rfc793">RFC 793</a>, DARPA, September 1981.
910
911 [<a id="ref-5">5</a>] Cheriton, D., "VMTP: Versatile Message Transaction Protocol", <a href="./rfc1045">RFC</a>
912 <a href="./rfc1045">1045</a>, Stanford University, February 1988.
913
914 Authors' Addresses
915
916 Kirk Lougheed
917 cisco Systems, Inc.
918 1360 Willow Road, Suite 201
919 Menlo Park, CA 94025
920
921 Phone: (415) 326-1941
922
923 Email: [email protected]
924
925
926 Jacob Rekhter
927 T.J. Watson Research Center
928 IBM Corporation
929 P.O. Box 218
930 Yorktown Heights, NY 10598
931
932 Phone: (914) 945-3896
933
934 Email: [email protected]
935
936
937
938
939
940
941
942
943
944
945
946
947
948 Lougheed &amp; Rekhter [Page 17]
949 </pre>