Changeset 1611

Show
Ignore:
Timestamp:
06/21/09 19:39:37 (9 months ago)
Author:
eriol
Message:

Closes #46 --- Cleanup + fixed netid update problem discovered by jnz

Files:

Legend:

Unmodified
Added
Removed
Modified
Copied
Moved

  • netsukuku/trunk/pyntk/ntk/core/qspn.py

    r1581 r1611  
    44# 
    55# This source code is free software; you can redistribute it and/or 
    6 # modify it under the terms of the GNU General Public License as published  
     6# modify it under the terms of the GNU General Public License as published 
    77# by the Free Software Foundation; either version 2 of the License, 
    88# or (at your option) any later version. 
    …… 
    1818## 
    1919 
     20from operator import add 
     21 
     22from ntk.core.route import NullRem, DeadRem 
     23from ntk.lib.event import Event 
    2024from ntk.lib.micro import microfunc 
    21 from ntk.lib.event import Event 
    22 from ntk.core.route import NullRem, DeadRem 
    2325 
    2426def is_listlist_empty(l): 
    25         """ 
    26             Returns true if l=[[],[], ...] 
    27             l is a list of lists. 
    28         """ 
    29         return not any(l) 
    30  
    31 class Etp: 
     27    """Returns true if l=[[],[], ...] 
     28    :type l: a list of lists. 
     29    """ 
     30    return not any(l) 
     31 
     32class Etp(object): 
    3233    """Extended Tracer Packet""" 
    3334 
    3435    def __init__(self, radar, maproute): 
    3536 
    36         self.neigh   =radar.neigh 
    37         self.netid   =radar.netid 
    38         self.maproute=maproute 
     37        self.radar = radar 
     38        self.neigh = radar.neigh 
     39        self.maproute = maproute 
    3940 
    4041        self.neigh.events.listen('NEIGH_NEW', self.etp_new_changed) 
    …… 
    5253        ## Create R 
    5354        def gw_is_neigh((dst, gw, rem)): 
    54                 return gw == neigh.id 
    55         R=self.maproute.bestroutes_get(gw_is_neigh) 
     55            return gw == neigh.id 
     56        R = self.maproute.bestroutes_get(gw_is_neigh) 
    5657        ## 
    5758 
    …… 
    6162 
    6263        if is_listlist_empty(R): 
    63                 # R is empty, that is we don't have routes passing by `gw'. 
    64                 # Therefore, nothing to update, nothing to do. 
    65                 return 
    66          
     64            # R is empty, that is we don't have routes passing by `gw'. 
     65            # Therefore, nothing to update, nothing to do. 
     66            return None 
     67 
    6768        ## Create R2 
    6869        def rem_or_none(r): 
    69                 if r is not None: 
    70                         return r.rem 
    71                 return DeadRem() 
    72  
    73         R2 = [  
     70            if r is not None: 
     71                return r.rem 
     72            return DeadRem() 
     73 
     74        R2 = [ 
    7475              [ (dst, rem_or_none(self.maproute.node_get(lvl, dst).best_route())) 
    7576                    for (dst,gw,rem) in R[lvl] 
    …… 
    101102        ## Create R 
    102103        def gw_isnot_neigh((dst, gw, rem)): 
    103                 return gw != neigh.id 
     104            return gw != neigh.id 
     105 
    104106        R = self.maproute.bestroutes_get(gw_isnot_neigh) 
     107 
    105108        if is_listlist_empty(R): 
    106                 # R is empty: no need to proceed 
    107                 return 
     109            # R is empty: no need to proceed 
     110            return None 
    108111 
    109112        def takeoff_gw((dst, gw, rem)): 
    110                 return (dst, rem) 
     113            return (dst, rem) 
     114 
    111115        def takeoff_gw_lvl(L): 
    112                 return map(takeoff_gw, L) 
    113         R=map(takeoff_gw_lvl, R) 
     116            return map(takeoff_gw, L) 
     117 
     118        R = map(takeoff_gw_lvl, R) 
    114119        ## 
    115120 
    …… 
    124129    def etp_exec(self, sender_nip, R, TPL, flag_of_interest): 
    125130        """Executes a received ETP 
    126          
     131 
    127132        sender_nip: sender ntk ip (see map.py) 
    128133        R  : the set of routes of the ETP 
    129134        TPL: the tracer packet of the path covered until now by this ETP. 
    130              This TP may have covered different levels. In general, TPL  
     135             This TP may have covered different levels. In general, TPL 
    131136             is a list of blocks. Each block is a (lvl, TP) pair, where lvl is 
    132137             the level of the block and TP is the tracer packet composed 
    …… 
    136141        """ 
    137142 
    138         gwnip   = sender_nip 
    139         neigh   = self.neigh.ip_to_neigh(self.maproute.nip_to_ip(gwnip)) 
    140         gw      = neigh.id 
    141         gwrem   = neigh.rem 
     143        gwnip = sender_nip 
     144        neigh = self.neigh.ip_to_neigh(self.maproute.nip_to_ip(gwnip)) 
     145        gw = neigh.id 
     146        gwrem = neigh.rem 
    142147 
    143148        ## Collision check 
    144149        colliding, R = self.collision_check(gwnip, neigh, R) 
    145150        if colliding: 
    146                 # collision detected. rehook. 
    147                 self.events.send('NET_COLLISION',  
    148                                  ([nr for nr in self.neigh.neigh_list() 
    149                                                 if nr.netid == neigh.netid],) 
    150                                 ) 
    151                 return # drop the packet 
     151            # collision detected. rehook. 
     152            self.events.send('NET_COLLISION', 
     153                             ([nr for nr in self.neigh.neigh_list() 
     154                                      if nr.netid == neigh.netid],) 
     155            ) 
     156            return None # drop the packet 
    152157        ## 
    153158 
    …… 
    155160        level = self.maproute.nip_cmp(self.maproute.me, gwnip) 
    156161        for block in TPL: 
    157                 lvl = block[0] # the level of the block 
    158                 if lvl < level: 
    159                         block[0] = level                      
    160                         blockrem = sum([rem for hop, rem in block[1]], NullRem()) 
    161                         block[1] = [[gwnip[level], blockrem]] 
    162                         R[lvl] = [] 
    163          
    164          
     162            lvl = block[0] # the level of the block 
     163            if lvl < level: 
     164                block[0] = level 
     165                blockrem = sum([rem for hop, rem in block[1]], NullRem()) 
     166                block[1] = [[gwnip[level], blockrem]] 
     167                R[lvl] = [] 
     168 
     169 
    165170        ### Collapse blocks of the same level 
    166171        #Note: we're assuming the two blocks with the same level are one after 
    167172        #      another. 
    168         TPL2=[TPL[0]] 
     173        TPL2 = [TPL[0]] 
     174 
    169175        for block in TPL[1:]: 
    170                 if block[0] == TPL2[-1][0]: 
    171                         TPL2[-1][1]+=block[1] 
    172                 else: 
    173                         TPL2.append(block) 
    174         TPL=TPL2 
     176            if block[0] == TPL2[-1][0]: 
     177                TPL2[-1][1]+=block[1] 
     178            else: 
     179                TPL2.append(block) 
     180        TPL = TPL2 
    175181        ### 
    176          
     182 
    177183        ### Remove dups 
    178184        def remove_contiguos_dups_in_TP(L): 
    179                 L2=[] 
    180                 prec=[None, NullRem()] 
    181                 for x in L: 
    182                         if x[0] != prec[0]: 
    183                                 prec=x 
    184                                 L2.append(x) 
    185                         else: 
    186                                 prec[1]+=x[1] 
    187                 return L2 
     185            L2 = [] 
     186            prec = [None, NullRem()] 
     187            for x in L: 
     188                if x[0] != prec[0]: 
     189                    prec = x 
     190                    L2.append(x) 
     191                else: 
     192                    prec[1] += x[1] 
     193            return L2 
    188194 
    189195        for block in TPL: 
    190                 block[1]=remove_contiguos_dups_in_TP(block[1]) 
     196            block[1] = remove_contiguos_dups_in_TP(block[1]) 
    191197        ### 
    192198 
    …… 
    195201        ## ATP rule 
    196202        for block in TPL: 
    197                 if self.maproute.me[block[0]] in block[1]: 
    198                         return    # drop the pkt 
     203            if self.maproute.me[block[0]] in block[1]: 
     204                return    # drop the pkt 
    199205        ## 
    200206 
    …… 
    206212 
    207213        ## Update the map from the TPL 
    208         tprem=gwrem 
     214        tprem = gwrem 
    209215        TPL_is_interesting = False 
    210216        for block in reversed(TPL): 
    …… 
    229235                        if r.gw != gw 
    230236              ] for lvl in xrange(self.maproute.levels) ] 
    231         
     237 
    232238        #-- 
    233239        # Step 5 omitted, see qspn.pdf, 4.1 Extended Tracer Packet: 
    …… 
    243249        ## 
    244250 
    245         ## R2  
     251        ## R2 
    246252        R2 = [ [ (dst, rem) 
    247253                for dst, rem in R[lvl] 
    …… 
    253259 
    254260        if not is_listlist_empty(R2) or TPL_is_interesting: 
    255                 if TPL[-1][0] != 0:  
    256                         # The last block isn't of level 0. Let's add a new block 
    257                         TP = [[self.maproute.me[0], gwrem]]  
    258                         TPL.append([0, TP]) 
    259                 else: 
    260                         # The last block is of level 0. We can append our ID 
    261                         TPL[-1][1].append([self.maproute.me[0], gwrem]) 
    262  
    263  
    264                 etp = (R2, TPL, flag_of_interest) 
    265                 self.etp_forward(etp, [neigh.id]) 
     261            if TPL[-1][0] != 0: 
     262                # The last block isn't of level 0. Let's add a new block 
     263                TP = [[self.maproute.me[0], gwrem]] 
     264                TPL.append([0, TP]) 
     265            else: 
     266                # The last block is of level 0. We can append our ID 
     267                TPL[-1][1].append([self.maproute.me[0], gwrem]) 
     268 
     269 
     270            etp = (R2, TPL, flag_of_interest) 
     271            self.etp_forward(etp, [neigh.id]) 
    266272        ## 
    267273 
    …… 
    271277        """Forwards the `etp' to all our neighbours, 
    272278           excluding those contained in `exclude' 
    273             
     279 
    274280           `Exclude' is a list of "Neighbour.id"s""" 
    275281 
    276282        for nr in self.neigh.neigh_list(): 
    277                 if nr.id not in exclude: 
    278                         nr.ntkd.etp.etp_exec(self.maproute.me, *etp) 
    279      
     283            if nr.id not in exclude: 
     284                nr.ntkd.etp.etp_exec(self.maproute.me, *etp) 
     285 
    280286    def collision_check(self, gwnip, neigh, R): 
    281287        """ Checks if we are colliding with the network of `neigh'. 
    282          
     288 
    283289            It returns True if we are colliding and we are going to rehook. 
    284290            !NOTE! the set R will be modified: all the colliding routes will 
    285291            be removed. 
    286292        """ 
    287          
    288         if neigh.netid == self.netid                              \ 
    289             or self.netid == -1: 
    290                 self.netid = neigh.netid 
    291                 return (False, R) # all ok 
     293 
     294        if neigh.netid == self.radar.netid or self.radar.netid == -1: 
     295            self.radar.netid = neigh.netid 
     296            return (False, R) # all ok 
    292297 
    293298        # uhm... we are in different networks 
    294299 
    295300        ## Calculate the size of the two nets 
    296         def add(a,b):return a+b 
    297301        mynetsz = reduce(add, self.maproute.node_nb) 
    298302        ngnetsz = reduce(add, map(len, R)) 
    299303 
    300         if mynetsz > ngnetsz or                                         \ 
    301                 (mynetsz == ngnetsz and self.netid > neigh.netid): 
     304        if mynetsz > ngnetsz or \ 
     305           (mynetsz == ngnetsz and self.radar.netid > neigh.netid): 
    302306                # we don't care if we are colliding or not. We can simply 
    303307                # ignore colliding routes, the rest will be done by the other 
    …… 
    305309 
    306310                ### Remove colliding routes from R 
    307                 R = [ [ (dst, rem)  
    308                             for dst, rem in R[lvl] 
    309                                 if self.maproute.node_get(lvl, dst).is_empty() ] 
    310                         for lvl in xrange(self.maproute.levels) ] 
     311                R = [[(dst, rem) for dst, rem in R[lvl] 
     312                        if self.maproute.node_get(lvl, dst).is_empty() 
     313                     ] 
     314                     for lvl in xrange(self.maproute.levels) 
     315                ] 
    311316                ### 
    312317                return (False, R) 
    …… 
    319324        level = self.maproute.nip_cmp(self.maproute.me, gwnip) + 1 
    320325        if level < self.maproute.levels: 
    321                 for dst, rem in R[level]: 
    322                         if dst == self.maproute.me[level]: 
    323                                 # we are colliding! LET'S REHOOK 
    324                                 return (True, R) 
    325         ##  
     326            for dst, rem in R[level]: 
     327                if dst == self.maproute.me[level]: 
     328                    # we are colliding! LET'S REHOOK 
     329                    return (True, R) 
     330        ## 
    326331 
    327332        ## Remove colliding routes directly from our map 
    328333        for lvl in xrange(self.maproute.levels): 
    329                 for dst, rem in R[lvl]: 
    330                         self.maproute.node_get(lvl, dst).route_reset() 
     334            for dst, rem in R[lvl]: 
     335                self.maproute.node_get(lvl, dst).route_reset() 
    331336        ## 
    332337 
    333338        return (False, R) 
    334