ryu/build/lib.linux-armv7l-2.7/ryu/services/protocols/bgp/processor.py

   1 # Copyright (C) 2014 Nippon Telegraph and Telephone Corporation.
   2 #
   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
   6 #
   7 #    http://www.apache.org/licenses/LICENSE-2.0
   8 #
   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
  12 # implied.
  13 # See the License for the specific language governing permissions and
  14 # limitations under the License.
  15 """
  16  Module related to processing bgp paths.
  17 """
  18
  19 import logging
  20
  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
  27
  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
  38
  39 LOG = logging.getLogger('bgpspeaker.processor')
  40
  41
  42 @add_bgp_error_metadata(code=BGP_PROCESSOR_ERROR_CODE, sub_code=1,
  43                         def_desc='Error occurred when processing bgp '
  44                         'destination.')
  45 class BgpProcessorError(BGPSException):
  46     """Base exception related to all destination path processing errors.
  47     """
  48     pass
  49
  50
  51 # Disabling known bug in pylint.
  52 # pylint: disable=R0921
  53 class BgpProcessor(Activity):
  54     """Worker that processes queued `Destination'.
  55
  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.
  61     """
  62
  63     # Max. number of destinations processed per cycle.
  64     MAX_DEST_PROCESSED_PER_CYCLE = 100
  65
  66     #
  67     # DestQueue
  68     #
  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'
  71     # attributes.
  72     #
  73     _DestQueue = circlist.CircularListType(
  74         next_attr_name='next_dest_to_process',
  75         prev_attr_name='prev_dest_to_process')
  76
  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
  86
  87     def _run(self, *args, **kwargs):
  88         # Sit in tight loop, getting destinations from the queue and processing
  89         # one at a time.
  90         while True:
  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()
  95
  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
  98             # greenthread to run)
  99             self._process_dest()
 100
 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()
 105             else:
 106                 self.pause(0)
 107
 108     def _process_dest(self):
 109         dest_processed = 0
 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()
 115             if next_dest:
 116                 next_dest.process()
 117                 dest_processed += 1
 118
 119     def _process_rtdest(self):
 120         LOG.debug('Processing RT NLRI destination...')
 121         if self._rtdest_queue.is_empty():
 122             return
 123         else:
 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()
 128                 if next_dest:
 129                     next_dest.process()
 130                     processed_any = True
 131
 132             if processed_any:
 133                 # Since RT destination were updated we update RT filters
 134                 self._core_service.update_rtfilters()
 135
 136     def enqueue(self, destination):
 137         """Enqueues given destination for processing.
 138
 139         Given instance should be a valid destination.
 140         """
 141         if not destination:
 142             raise BgpProcessorError('Invalid destination %s.' % destination)
 143
 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
 148
 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)
 153
 154         # Wake-up processing thread if sleeping.
 155         self.dest_que_evt.set()
 156
 157
 158 # =============================================================================
 159 # Best path computation related utilities.
 160 # =============================================================================
 161
 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'
 171 BPR_MED = 'MED'
 172 BPR_ASN = 'ASN'
 173 BPR_IGP_COST = 'IGP Cost'
 174 BPR_ROUTER_ID = 'Router ID'
 175 BPR_CLUSTER_LIST = 'Cluster List'
 176
 177
 178 def _compare_by_version(path1, path2):
 179     """Returns the current/latest learned path.
 180
 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.
 184     """
 185     if path1.source == path2.source:
 186         if path1.source_version_num > path2.source_version_num:
 187             return path1
 188         else:
 189             return path2
 190     return None
 191
 192
 193 def compute_best_path(local_asn, path1, path2):
 194     """Compares given paths and returns best path.
 195
 196     Parameters:
 197         -`local_asn`: asn of local bgpspeaker
 198         -`path1`: first path to compare
 199         -`path2`: second path to compare
 200
 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
 211         Incomplete.
 212     7.  If the origins are the same, select the path with lowest MED
 213         value.
 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
 218         router ID.
 219     11. Select the route received from the peer with the shorter
 220         CLUSTER_LIST length.
 221
 222     Returns None if best-path among given paths cannot be computed else best
 223     path.
 224     Assumes paths from NC has source equal to None.
 225     """
 226     best_path = None
 227     best_path_reason = BPR_UNKNOWN
 228
 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
 265
 266     return best_path, best_path_reason
 267
 268
 269 def _cmp_by_reachable_nh(path1, path2):
 270     """Compares given paths and selects best path based on reachable next-hop.
 271
 272     If no path matches this criteria, return None.
 273     """
 274     # TODO(PH): Currently we do not have a way to check if a IGP route to
 275     # NEXT_HOP exists from BGPS.
 276     return None
 277
 278
 279 def _cmp_by_highest_wg(path1, path2):
 280     """Selects a path with highest weight.
 281
 282     Weight is BGPS specific parameter. It is local to the router on which it
 283      is configured.
 284     Return:
 285         None if best path among given paths cannot be decided, else best path.
 286     """
 287     # TODO(PH): Revisit this when BGPS has concept of policy to be applied to
 288     # in-bound NLRIs.
 289     return None
 290
 291
 292 def _cmp_by_local_pref(path1, path2):
 293     """Selects a path with highest local-preference.
 294
 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,
 298     we return None.
 299     """
 300     # TODO(PH): Revisit this when BGPS has concept of policy to be applied to
 301     # in-bound NLRIs.
 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):
 306         return None
 307
 308     # Highest local-preference value is preferred.
 309     lp1 = lp1.value
 310     lp2 = lp2.value
 311     if lp1 > lp2:
 312         return path1
 313     elif lp2 > lp1:
 314         return path2
 315     else:
 316         return None
 317
 318
 319 def _cmp_by_local_origin(path1, path2):
 320     """Select locally originating path as best path.
 321
 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.
 327     """
 328     # If both paths are from same sources we cannot compare them here.
 329     if path1.source == path2.source:
 330         return None
 331
 332     # Here we consider prefix from NC as locally originating static route.
 333     # Hence it is preferred.
 334     if path1.source is None:
 335         return path1
 336
 337     if path2.source is None:
 338         return path2
 339
 340     return None
 341
 342
 343 def _cmp_by_aspath(path1, path2):
 344     """Calculated the best-paths by comparing as-path lengths.
 345
 346     Shortest as-path length is preferred. If both path have same lengths,
 347     we return None.
 348     """
 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
 355     if l1 > l2:
 356         return path2
 357     elif l2 > l1:
 358         return path1
 359     else:
 360         return None
 361
 362
 363 def _cmp_by_origin(path1, path2):
 364     """Select the best path based on origin attribute.
 365
 366     IGP is preferred over EGP; EGP is preferred over Incomplete.
 367     If both paths have same origin, we return None.
 368     """
 369     def get_origin_pref(origin):
 370         if origin.value == BGP_ATTR_ORIGIN_IGP:
 371             return 3
 372         elif origin.value == BGP_ATTR_ORIGIN_EGP:
 373             return 2
 374         elif origin.value == BGP_ATTR_ORIGIN_INCOMPLETE:
 375             return 1
 376         else:
 377             LOG.error('Invalid origin value encountered %s.', origin)
 378             return 0
 379
 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
 383
 384     # If both paths have same origins
 385     if origin1.value == origin2.value:
 386         return None
 387
 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:
 393         return None
 394     elif origin1 > origin2:
 395         return path1
 396     return path2
 397
 398
 399 def _cmp_by_med(path1, path2):
 400     """Select the path based with lowest MED value.
 401
 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.
 406     """
 407     def get_path_med(path):
 408         med = path.get_pattr(BGP_ATTR_TYPE_MULTI_EXIT_DISC)
 409         if not med:
 410             return 0
 411         return med.value
 412
 413     med1 = get_path_med(path1)
 414     med2 = get_path_med(path2)
 415
 416     if med1 == med2:
 417         return None
 418     elif med1 < med2:
 419         return path1
 420     return path2
 421
 422
 423 def _cmp_by_asn(local_asn, path1, path2):
 424     """Select the path based on source (iBGP/eBGP) peer.
 425
 426     eBGP path is preferred over iBGP. If both paths are from same kind of
 427     peers, return None.
 428     """
 429     def get_path_source_asn(path):
 430         asn = None
 431         if path.source is None:
 432             asn = local_asn
 433         else:
 434             asn = path.source.remote_as
 435         return asn
 436
 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):
 441         return path2
 442
 443     # If path2 is from ibgp peer and path1 is from ebgp peer,
 444     if (p2_asn == local_asn) and (p1_asn != local_asn):
 445         return path1
 446
 447     # If both paths are from ebgp or ibpg peers, we cannot decide.
 448     return None
 449
 450
 451 def _cmp_by_igp_cost(path1, path2):
 452     """Select the route with the lowest IGP cost to the next hop.
 453
 454     Return None if igp cost is same.
 455     """
 456     # TODO(PH): Currently BGPS has no concept of IGP and IGP cost.
 457     return None
 458
 459
 460 def _cmp_by_router_id(local_asn, path1, path2):
 461     """Select the route received from the peer with the lowest BGP router ID.
 462
 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.
 467     """
 468     def get_asn(path_source):
 469         if path_source is None:
 470             return local_asn
 471         else:
 472             return path_source.remote_as
 473
 474     def get_router_id(path, local_bgp_id):
 475         path_source = path.source
 476         if path_source is None:
 477             return local_bgp_id
 478         else:
 479             originator_id = path.get_pattr(BGP_ATTR_TYPE_ORIGINATOR_ID)
 480             if originator_id:
 481                 return originator_id.value
 482             return path_source.protocol.recv_open_msg.bgp_identifier
 483
 484     path_source1 = path1.source
 485     path_source2 = path2.source
 486
 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:
 489         return None
 490
 491     asn1 = get_asn(path_source1)
 492     asn2 = get_asn(path_source2)
 493
 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:
 499         return None
 500
 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'
 504                          ' ibgp path')
 505
 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
 509     else:
 510         local_bgp_id = path_source2.protocol.sent_open_msg.bgp_identifier
 511
 512     # Get router ids.
 513     router_id1 = get_router_id(path1, local_bgp_id)
 514     router_id2 = get_router_id(path2, local_bgp_id)
 515
 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:
 519         return None
 520
 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):
 524         return path1
 525     else:
 526         return path2
 527
 528
 529 def _cmp_by_cluster_list(path1, path2):
 530     """Selects the route received from the peer with the shorter
 531     CLUSTER_LIST length. [RFC4456]
 532
 533     The CLUSTER_LIST length is evaluated as zero if a route does not
 534     carry the CLUSTER_LIST attribute.
 535     """
 536     def _get_cluster_list_len(path):
 537         c_list = path.get_pattr(BGP_ATTR_TYPE_CLUSTER_LIST)
 538         if c_list is None:
 539             return 0
 540         else:
 541             return len(c_list.value)
 542
 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:
 546         return path1
 547     elif c_list_len1 > c_list_len2:
 548         return path2
 549     else:
 550         return None