1 # Copyright (C) 2014 Nippon Telegraph and Telephone Corporation.
3 # Licensed under the Apache License, Version 2.0 (the "License");
4 # you may not use this file except in compliance with the License.
5 # You may obtain a copy of the License at
7 # http://www.apache.org/licenses/LICENSE-2.0
9 # Unless required by applicable law or agreed to in writing, software
10 # distributed under the License is distributed on an "AS IS" BASIS,
11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
13 # See the License for the specific language governing permissions and
14 # limitations under the License.
16 Module related to processing bgp paths.
21 from ryu.services.protocols.bgp.base import Activity
22 from ryu.services.protocols.bgp.base import add_bgp_error_metadata
23 from ryu.services.protocols.bgp.base import BGP_PROCESSOR_ERROR_CODE
24 from ryu.services.protocols.bgp.base import BGPSException
25 from ryu.services.protocols.bgp.utils import circlist
26 from ryu.services.protocols.bgp.utils.evtlet import EventletIOFactory
28 from ryu.lib.packet.bgp import RF_RTC_UC
29 from ryu.lib.packet.bgp import BGP_ATTR_TYPE_AS_PATH
30 from ryu.lib.packet.bgp import BGP_ATTR_TYPE_LOCAL_PREF
31 from ryu.lib.packet.bgp import BGP_ATTR_TYPE_MULTI_EXIT_DISC
32 from ryu.lib.packet.bgp import BGP_ATTR_TYPE_ORIGIN
33 from ryu.lib.packet.bgp import BGP_ATTR_TYPE_ORIGINATOR_ID
34 from ryu.lib.packet.bgp import BGP_ATTR_TYPE_CLUSTER_LIST
35 from ryu.lib.packet.bgp import BGP_ATTR_ORIGIN_IGP
36 from ryu.lib.packet.bgp import BGP_ATTR_ORIGIN_EGP
37 from ryu.lib.packet.bgp import BGP_ATTR_ORIGIN_INCOMPLETE
39 LOG = logging.getLogger('bgpspeaker.processor')
42 @add_bgp_error_metadata(code=BGP_PROCESSOR_ERROR_CODE, sub_code=1,
43 def_desc='Error occurred when processing bgp '
45 class BgpProcessorError(BGPSException):
46 """Base exception related to all destination path processing errors.
51 # Disabling known bug in pylint.
52 # pylint: disable=R0921
53 class BgpProcessor(Activity):
54 """Worker that processes queued `Destination'.
56 `Destination` that have updates related to its paths need to be
57 (re)processed. Only one instance of this processor is enough for normal
58 cases. If you want more control on which destinations get processed faster
59 compared to other destinations, you can create several instance of this
60 works to achieve the desired work flow.
63 # Max. number of destinations processed per cycle.
64 MAX_DEST_PROCESSED_PER_CYCLE = 100
69 # A circular list type in which objects are linked to each
70 # other using the 'next_dest_to_process' and 'prev_dest_to_process'
73 _DestQueue = circlist.CircularListType(
74 next_attr_name='next_dest_to_process',
75 prev_attr_name='prev_dest_to_process')
77 def __init__(self, core_service, work_units_per_cycle=None):
78 Activity.__init__(self)
79 # Back pointer to core service instance that created this processor.
80 self._core_service = core_service
81 self._dest_queue = BgpProcessor._DestQueue()
82 self._rtdest_queue = BgpProcessor._DestQueue()
83 self.dest_que_evt = EventletIOFactory.create_custom_event()
84 self.work_units_per_cycle =\
85 work_units_per_cycle or BgpProcessor.MAX_DEST_PROCESSED_PER_CYCLE
87 def _run(self, *args, **kwargs):
88 # Sit in tight loop, getting destinations from the queue and processing
91 LOG.debug('Starting new processing run...')
92 # We process all RT destination first so that we get a new RT
93 # filter that apply for each peer
94 self._process_rtdest()
96 # We then process a batch of other destinations (we do not process
97 # all destination here as we want to give change to other
101 if self._dest_queue.is_empty():
102 # If we have no destinations queued for processing, we wait.
103 self.dest_que_evt.clear()
104 self.dest_que_evt.wait()
108 def _process_dest(self):
110 LOG.debug('Processing destination...')
111 while (dest_processed < self.work_units_per_cycle and
112 not self._dest_queue.is_empty()):
113 # We process the first destination in the queue.
114 next_dest = self._dest_queue.pop_first()
119 def _process_rtdest(self):
120 LOG.debug('Processing RT NLRI destination...')
121 if self._rtdest_queue.is_empty():
124 processed_any = False
125 while not self._rtdest_queue.is_empty():
126 # We process the first destination in the queue.
127 next_dest = self._rtdest_queue.pop_first()
133 # Since RT destination were updated we update RT filters
134 self._core_service.update_rtfilters()
136 def enqueue(self, destination):
137 """Enqueues given destination for processing.
139 Given instance should be a valid destination.
142 raise BgpProcessorError('Invalid destination %s.' % destination)
144 dest_queue = self._dest_queue
145 # RtDest are queued in a separate queue
146 if destination.route_family == RF_RTC_UC:
147 dest_queue = self._rtdest_queue
149 # We do not add given destination to the queue for processing if
150 # it is already on the queue.
151 if not dest_queue.is_on_list(destination):
152 dest_queue.append(destination)
154 # Wake-up processing thread if sleeping.
155 self.dest_que_evt.set()
158 # =============================================================================
159 # Best path computation related utilities.
160 # =============================================================================
162 # Various reasons a path is chosen as best path.
163 BPR_UNKNOWN = 'Unknown'
164 BPR_ONLY_PATH = 'Only Path'
165 BPR_REACHABLE_NEXT_HOP = 'Reachable Next Hop'
166 BPR_HIGHEST_WEIGHT = 'Highest Weight'
167 BPR_LOCAL_PREF = 'Local Pref'
168 BPR_LOCAL_ORIGIN = 'Local Origin'
169 BPR_ASPATH = 'AS Path'
170 BPR_ORIGIN = 'Origin'
173 BPR_IGP_COST = 'IGP Cost'
174 BPR_ROUTER_ID = 'Router ID'
175 BPR_CLUSTER_LIST = 'Cluster List'
178 def _compare_by_version(path1, path2):
179 """Returns the current/latest learned path.
181 Checks if given paths are from same source/peer and then compares their
182 version number to determine which path is received later. If paths are from
183 different source/peer return None.
185 if path1.source == path2.source:
186 if path1.source_version_num > path2.source_version_num:
193 def compute_best_path(local_asn, path1, path2):
194 """Compares given paths and returns best path.
197 -`local_asn`: asn of local bgpspeaker
198 -`path1`: first path to compare
199 -`path2`: second path to compare
201 Best path processing will involve following steps:
202 1. Select a path with a reachable next hop.
203 2. Select the path with the highest weight.
204 3. If path weights are the same, select the path with the highest
205 local preference value.
206 4. Prefer locally originated routes (network routes, redistributed
207 routes, or aggregated routes) over received routes.
208 5. Select the route with the shortest AS-path length.
209 6. If all paths have the same AS-path length, select the path based
210 on origin: IGP is preferred over EGP; EGP is preferred over
212 7. If the origins are the same, select the path with lowest MED
214 8. If the paths have the same MED values, select the path learned
215 via EBGP over one learned via IBGP.
216 9. Select the route with the lowest IGP cost to the next hop.
217 10. Select the route received from the peer with the lowest BGP
219 11. Select the route received from the peer with the shorter
222 Returns None if best-path among given paths cannot be computed else best
224 Assumes paths from NC has source equal to None.
227 best_path_reason = BPR_UNKNOWN
229 # Follow best path calculation algorithm steps.
230 if best_path is None:
231 best_path = _cmp_by_reachable_nh(path1, path2)
232 best_path_reason = BPR_REACHABLE_NEXT_HOP
233 if best_path is None:
234 best_path = _cmp_by_highest_wg(path1, path2)
235 best_path_reason = BPR_HIGHEST_WEIGHT
236 if best_path is None:
237 best_path = _cmp_by_local_pref(path1, path2)
238 best_path_reason = BPR_LOCAL_PREF
239 if best_path is None:
240 best_path = _cmp_by_local_origin(path1, path2)
241 best_path_reason = BPR_LOCAL_ORIGIN
242 if best_path is None:
243 best_path = _cmp_by_aspath(path1, path2)
244 best_path_reason = BPR_ASPATH
245 if best_path is None:
246 best_path = _cmp_by_origin(path1, path2)
247 best_path_reason = BPR_ORIGIN
248 if best_path is None:
249 best_path = _cmp_by_med(path1, path2)
250 best_path_reason = BPR_MED
251 if best_path is None:
252 best_path = _cmp_by_asn(local_asn, path1, path2)
253 best_path_reason = BPR_ASN
254 if best_path is None:
255 best_path = _cmp_by_igp_cost(path1, path2)
256 best_path_reason = BPR_IGP_COST
257 if best_path is None:
258 best_path = _cmp_by_router_id(local_asn, path1, path2)
259 best_path_reason = BPR_ROUTER_ID
260 if best_path is None:
261 best_path = _cmp_by_cluster_list(path1, path2)
262 best_path_reason = BPR_CLUSTER_LIST
263 if best_path is None:
264 best_path_reason = BPR_UNKNOWN
266 return best_path, best_path_reason
269 def _cmp_by_reachable_nh(path1, path2):
270 """Compares given paths and selects best path based on reachable next-hop.
272 If no path matches this criteria, return None.
274 # TODO(PH): Currently we do not have a way to check if a IGP route to
275 # NEXT_HOP exists from BGPS.
279 def _cmp_by_highest_wg(path1, path2):
280 """Selects a path with highest weight.
282 Weight is BGPS specific parameter. It is local to the router on which it
285 None if best path among given paths cannot be decided, else best path.
287 # TODO(PH): Revisit this when BGPS has concept of policy to be applied to
292 def _cmp_by_local_pref(path1, path2):
293 """Selects a path with highest local-preference.
295 Unlike the weight attribute, which is only relevant to the local
296 router, local preference is an attribute that routers exchange in the
297 same AS. Highest local-pref is preferred. If we cannot decide,
300 # TODO(PH): Revisit this when BGPS has concept of policy to be applied to
302 # Default local-pref values is 100
303 lp1 = path1.get_pattr(BGP_ATTR_TYPE_LOCAL_PREF)
304 lp2 = path2.get_pattr(BGP_ATTR_TYPE_LOCAL_PREF)
305 if not (lp1 and lp2):
308 # Highest local-preference value is preferred.
319 def _cmp_by_local_origin(path1, path2):
320 """Select locally originating path as best path.
322 Locally originating routes are network routes, redistributed routes,
323 or aggregated routes. For now we are going to prefer routes received
324 through a Flexinet-Peer as locally originating route compared to routes
325 received from a BGP peer.
326 Returns None if given paths have same source.
328 # If both paths are from same sources we cannot compare them here.
329 if path1.source == path2.source:
332 # Here we consider prefix from NC as locally originating static route.
333 # Hence it is preferred.
334 if path1.source is None:
337 if path2.source is None:
343 def _cmp_by_aspath(path1, path2):
344 """Calculated the best-paths by comparing as-path lengths.
346 Shortest as-path length is preferred. If both path have same lengths,
349 as_path1 = path1.get_pattr(BGP_ATTR_TYPE_AS_PATH)
350 as_path2 = path2.get_pattr(BGP_ATTR_TYPE_AS_PATH)
351 assert as_path1 and as_path2
352 l1 = as_path1.get_as_path_len()
353 l2 = as_path2.get_as_path_len()
354 assert l1 is not None and l2 is not None
363 def _cmp_by_origin(path1, path2):
364 """Select the best path based on origin attribute.
366 IGP is preferred over EGP; EGP is preferred over Incomplete.
367 If both paths have same origin, we return None.
369 def get_origin_pref(origin):
370 if origin.value == BGP_ATTR_ORIGIN_IGP:
372 elif origin.value == BGP_ATTR_ORIGIN_EGP:
374 elif origin.value == BGP_ATTR_ORIGIN_INCOMPLETE:
377 LOG.error('Invalid origin value encountered %s.', origin)
380 origin1 = path1.get_pattr(BGP_ATTR_TYPE_ORIGIN)
381 origin2 = path2.get_pattr(BGP_ATTR_TYPE_ORIGIN)
382 assert origin1 is not None and origin2 is not None
384 # If both paths have same origins
385 if origin1.value == origin2.value:
388 # Translate origin values to preference.
389 origin1 = get_origin_pref(origin1)
390 origin2 = get_origin_pref(origin2)
391 # Return preferred path.
392 if origin1 == origin2:
394 elif origin1 > origin2:
399 def _cmp_by_med(path1, path2):
400 """Select the path based with lowest MED value.
402 If both paths have same MED, return None.
403 By default, a route that arrives with no MED value is treated as if it
404 had a MED of 0, the most preferred value.
405 RFC says lower MED is preferred over higher MED value.
407 def get_path_med(path):
408 med = path.get_pattr(BGP_ATTR_TYPE_MULTI_EXIT_DISC)
413 med1 = get_path_med(path1)
414 med2 = get_path_med(path2)
423 def _cmp_by_asn(local_asn, path1, path2):
424 """Select the path based on source (iBGP/eBGP) peer.
426 eBGP path is preferred over iBGP. If both paths are from same kind of
429 def get_path_source_asn(path):
431 if path.source is None:
434 asn = path.source.remote_as
437 p1_asn = get_path_source_asn(path1)
438 p2_asn = get_path_source_asn(path2)
439 # If path1 is from ibgp peer and path2 is from ebgp peer.
440 if (p1_asn == local_asn) and (p2_asn != local_asn):
443 # If path2 is from ibgp peer and path1 is from ebgp peer,
444 if (p2_asn == local_asn) and (p1_asn != local_asn):
447 # If both paths are from ebgp or ibpg peers, we cannot decide.
451 def _cmp_by_igp_cost(path1, path2):
452 """Select the route with the lowest IGP cost to the next hop.
454 Return None if igp cost is same.
456 # TODO(PH): Currently BGPS has no concept of IGP and IGP cost.
460 def _cmp_by_router_id(local_asn, path1, path2):
461 """Select the route received from the peer with the lowest BGP router ID.
463 If both paths are eBGP paths, then we do not do any tie breaking, i.e we do
464 not pick best-path based on this criteria.
465 RFC: http://tools.ietf.org/html/rfc5004
466 We pick best path between two iBGP paths as usual.
468 def get_asn(path_source):
469 if path_source is None:
472 return path_source.remote_as
474 def get_router_id(path, local_bgp_id):
475 path_source = path.source
476 if path_source is None:
479 originator_id = path.get_pattr(BGP_ATTR_TYPE_ORIGINATOR_ID)
481 return originator_id.value
482 return path_source.protocol.recv_open_msg.bgp_identifier
484 path_source1 = path1.source
485 path_source2 = path2.source
487 # If both paths are from NC we have same router Id, hence cannot compare.
488 if path_source1 is None and path_source2 is None:
491 asn1 = get_asn(path_source1)
492 asn2 = get_asn(path_source2)
494 is_ebgp1 = asn1 != local_asn
495 is_ebgp2 = asn2 != local_asn
496 # If both paths are from eBGP peers, then according to RFC we need
497 # not tie break using router id.
498 if is_ebgp1 and is_ebgp2:
501 if ((is_ebgp1 is True and is_ebgp2 is False) or
502 (is_ebgp1 is False and is_ebgp2 is True)):
503 raise ValueError('This method does not support comparing ebgp with'
506 # At least one path is not coming from NC, so we get local bgp id.
507 if path_source1 is not None:
508 local_bgp_id = path_source1.protocol.sent_open_msg.bgp_identifier
510 local_bgp_id = path_source2.protocol.sent_open_msg.bgp_identifier
513 router_id1 = get_router_id(path1, local_bgp_id)
514 router_id2 = get_router_id(path2, local_bgp_id)
516 # If both router ids are same/equal we cannot decide.
517 # This case is possible since router ids are arbitrary.
518 if router_id1 == router_id2:
521 # Select the path with lowest router Id.
522 from ryu.services.protocols.bgp.utils.bgp import from_inet_ptoi
523 if from_inet_ptoi(router_id1) < from_inet_ptoi(router_id2):
529 def _cmp_by_cluster_list(path1, path2):
530 """Selects the route received from the peer with the shorter
531 CLUSTER_LIST length. [RFC4456]
533 The CLUSTER_LIST length is evaluated as zero if a route does not
534 carry the CLUSTER_LIST attribute.
536 def _get_cluster_list_len(path):
537 c_list = path.get_pattr(BGP_ATTR_TYPE_CLUSTER_LIST)
541 return len(c_list.value)
543 c_list_len1 = _get_cluster_list_len(path1)
544 c_list_len2 = _get_cluster_list_len(path2)
545 if c_list_len1 < c_list_len2:
547 elif c_list_len1 > c_list_len2: