IMPLEMENTING GARP MICK SEAMAN 7/96 - PURPOSE OF PRESENTATION - OBJECTIVES OF THE IMPLEMENTATION - THE GRAP MACHINE - USING THE GARP MACHINE ARRAY - TIMERS, EPOCHS, AND GRANULARITY - SOME PROCESSING DETAILS - rcv_join() - rcv_leave() - join_timer_expired() - leave_timer_expired() - OBSERVATIONS & RECOMMENDATIONS - TIMERS - CONTROLLING APPLICANTS - SPANNING TREE EFFECTS - POTENTIAL APPLICANTS - EXISTENCE AND MEMBERSHIP? - 'MODE' PROPAGATION AS INFORMATION - COMPRESSED PDU ENCODINGS - JOIN ALL EXCEPT :: PURPOSE OF PRESENTATION - ADDRESS FEARS RE. COMPLEXITY OF IMPLEMENTATION - SHARE SOME EXPERIENCE OF ATTEMPTING TO USE .1p/D3 - ENCOURAGE OTHERS TO DO LIKEWISE NOT: - TO PROPOSE A DEFINITIVE, COMPLETE OR EVEN FINISHED IMPLEMENTATION - OUR INTERNAL REFERENCE IMPLEMENTATION :: OBJECTIVES OF THE IMPLEMENTATION - COMPACT CODE - COMPACT DATASTRUCTURES FOR LARGE NUMBERS OF GROUPS AND BRIDGE PORTS - EASY PACKING OF JOINS, LEAVES, FOR MULTIPLE GROUPS INTO JOIN (LEAVE) PDUs - SMALL NUMBER OF SUPPORTING TIMERS - EXPLORE CONSEQUENCES OF SPECIFICATION - HAVE SOME FUN NOT: - PORTABLE CODE (NOT EVEN 'C' AT PRESENT) - A FLEXIBLE TEST BED FOR EXPERIMENTING WITH PROTOCOL ALTERNATIVES - AN EXERCISE IN OBJECT ORIENTED PROGRAMMING :: THE GARP MACHINE - REGISTRAR AND APPLICANT FOR A GROUP ON A PORT . . . . . . . . . Registrar. . Leave . . Applicant . . Join . . State . . Epoch . . State . . Epoch . |___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___| . . . . . . . . . . Manual/ . . Manual/ . . Admin . . Admin . . Control . . Control . . . . . . . Not in Update Send leave Send join Use filtering database - 16 bit, bit bumming, size for 32 bits? - Join and Leave Epochs - IDENTIFY THE TIME TICK (INCLUDING RANDOM COMPONENT) WHEN THE TIMER EXPIRES - 0 RESERVED FOR STOPPED - Applicant State - OUT, VERY ANXIOUS, LESS ANXIOUS, IN, NO (= MANUAL + OUT) - Registrar State - OUT, LEAVE IMMINENT, AWAIT REJOIN, IN, NO (= MANUAL + OUT), YES (= MANUAL + IN) :: USING THE GARP MACHINE ARRAY PORT1 PORT2 PORT3 PORT4 PORT5 PORT6 |-------------|-------|-------|-------|-------|-------|-------| | | | | | | | | |-------------|-------|-------|-------|-------|-------|-------| | GROUP ADDR. | | | | | | | |-------------|-------|-------|-------|-------|-------|-------| | | | | | | | | |-------------|-------|-------|-------|-------|-------|-------| | | | | | | | | |-------------|-------|-------|-------|-------|-------|-------| | | | | | | | | |-------------|-------|-------|-------|-------|-------|-------| - RECEIVE PDU OR PDUS ON A PORT, ACTION EACH DESCRIPTOR AGAINST GARP MACHINES FOR GROUP AND PORT, SETTING SEND JOIN, SEND LEAVE, UPDATE FILTERING DATABASE AS APPROPRIATE - AT END OF PDU(S) INITIATE HOLDING TIMER, ON HOLDING TIMER EXPIRY SWEEP GM ARRAY TO SEND PDUS ETC. - ON EPOCH TIMER EXPIRY SWEEP ARRAY FOR MATCHING EPOCHS, SET ACTION FLAGS AS APPROPRIATE, INITIATE HOLDING TIMER - ON SPANNING TREE CHANGE TO/FROM FORWARDING SWEEP MACHINE FOR PORT, SET ACTION FLAGS, INITIATE HOLDING TIMER :: TIMERS, EPOCHS, AND GRANULARITY - WHY NOT FIX TIMERS (PER MEDIA TYPE) :: SOME PROCESSING DETAILS [Partial extract] [Note, these have been revised since I presented in Twente, mainly because there seemed little point in continuing to present the incomplete code capable of dealing with both membership and existence machines - since we got rid of the existence set in Twente. Additionally the propagation of joins and leaves has been pulled into separate subroutines so they can be used for spanning tree port state transitions as well as individual group events. The major logic however remains as in Twente, and should continue to serve the purpose of indicating the order of processing complexity involved. WARNING: Don't bother to spend a lot of time debugging this code since I will be producing a number of comments on .1p/D4 which follow through on issues raised by Steve Horowitz on .1p/D3 - hence the code will doubtless change in its details.] /** BASIC CONSTANTS **/ /** DEFINED CONSTANTS **/ /* Garp machines, one per port */ #define Gm_not_in_use 0x8000 #define Gm_actions 0x0888 #define Gm_send_join 0x0008 #define Gm_send_leave 0x0080 #define Gm_updt_fdb 0x0800 #define Gapp 0x0077 #define X_gapp (~Gapp) #define Gapp_state 0x0070 #define Gapp_manual 0x0040 #define Gapp_no 0x0040 #define Gapp_out 0x0000 #define Gapp_vx 0x0010 #define Gapp_lx 0x0020 #define Gapp_in 0x0030 #define Gapp_jn_epoch 0x0007 #define Greg 0x7700 #define X_greg (~Greg) #define Greg_state 0x7000 #define Greg_manual 0x4000 #define Greg_auto 0x0000 #define Greg_no 0x4000 #define Greg_yes 0x7000 #define Greg_out 0x0000 #define Greg_lvim 0x1000 #define Greg_wtrj 0x2000 #define Greg_in 0x3000 #define Greg_lv_epoch 0x0700 #define X_greg_lv_epoch (~Greg_lv_epoch) /** PSEUDO-IMPLEMENTATION CONSTANTS **/ #define No_of_ports 16 #define Max_groups 255 /** DERIVED CONSTANTS **/ #define First_port 0 #define Last_port (No_of_ports - 1) #define All_ports (No_of_ports - 1) /** TYPEDEFS **/ Int16 Garp_machine; typedef struct { MAC_address group_addr; Garp_machine gm[All_ports]; } Group_record; /** GLOBAL VARIABLES **/ Group_record garp_database[Max_groups]; Garp_machine new_lv_epoch; Garp_machine new_jn_epoch; Garp_machine gapp_now_lx; /* Gapp_lx together with new_jn_epoch */ Garp_machine gapp_now_vx; /* Gapp_vx together with new_jn_epoch */ /** CODE **/ rcv_join(group,p) Group_record *group; Port p; { Garp_machine pm; Garp_machine pmrs; pm = group->gm[p]; /* Applicant for this Port: */ if ((pm & Gapp_state) == Gapp_vx) /* Very Anxious */ { /* becomes */ pm = (pm & X_gapp) | gapp_now_lx; /* Less Anxious, and restarts */ } /* join timer; */ else if ((pm & Gapp_state) == Gapp_lx) /* Less Anxious */ { /* becomes */ pm = (pm & X_gapp) | Gapp_in; /* In, and stops join timer; */ } /* else, i.e. No, Out, In, */ /* no change. */ pmrs = pm & Greg_state; if ((pmrs & Greg_manual) == Greg_auto) /* if Registrar for this Port not */ { /* manually configured, become */ pm = (pm & X_greg) | Greg_in; /* In, and stop leave timer. */ if (pmrs == Greg_out) /* if Registrar was Out: */ { /* */ pm = pm | Gm_updt_fdb; /* update Filtering Database, and */ /* */ if (port_state(p) = Forwarding) /* if this Port is Forwarding */ { /* */ propagate_join(group,p); /* propagate the join. */ } } } group->gm[p] = pm; } propagate_join(group,p) Group_record *group; Port p; { Port q; Garp_machine qm; for (q = First_port;q <= Last_port; q++) /* check all */ { /* */ if (q == p) continue; /* other Ports, */ /* else */ /* */ qm = group->gm[q]; /* if a Proxy Applicant */ if ((qm & Gapp_state) == Gapp_out) /* is Out, and its */ { /* */ if (port_state(q) == Forwarding) /* Port is Forwarding */ { /* */ qm = (qm & (X_gapp & (~Gm_send_leave))) /* cancel any pending */ | gapp_now_lx | Gm_send_join; /* leave, make Less */ /* Anxious,and send join.*/ group->gm[q] = qm; } } } /* end for(;;) */ } join_timer_expired(group,p) Group_record *group; Port p; { Garp_machine pm; pm = group->gm[p]; /* Applicant for this Port is either Very Anxious or */ /* Less Anxious: become In, stop join timer, and */ group->gm[p] = (pm & X_gapp) | Gapp_in | Gm_send_join; /* send join. */ } rcv_leave(group,p) Group_record *group; Port p; { Garp_machine pm; Garp_machine pmrs; pm = group->gm[p]; /* Applicant for this Port: */ if ((pm & (Gapp_state ^ Gapp_manual)) != Gapp_out) { /* Very Anxious, Less Anxious, In */ pm = (pm & X_gapp) | gapp_now_vx; /* become Very Anxious, and start */ } /* or restart join timer; */ /* Out or No ignore. */ pmrs = pm & Greg_state; /* Registrar for this Port: */ /* Await Rejoin, Leave Imminent, */ if ((pmrs == Greg_wtrj) || (pmrs == Greg_lvim) || (pmrs == Greg_in)) /* */ { /* In, start or restart */ pm = (pm & X_greg_lv_epoch) | new_lv_epoch; /* leave timer. */ /* */ if (pmrs == Greg_in) /* In becomes Await Rejoin. */ { pm = (pm ^ Greg_in) | Greg_wtrj; } } group->gm[p] = pm; } leave_timer_expired(group,p) Group_record *group; Port p; { Garp_machine pm; pm = group->gm[p]; /* Registrar for this Port is either Leave Imminent */ /* or Await Rejoin. */ if ((pm & Greg_state) == Greg_lvim) /* Registrar Leave Imminent: become */ { /* Out, stop leave timer, and update */ group->gm[p] = (pm & X_greg) | Greg_out | Gm_updt_fdb; /* Filtering */ /* Database. */ /* Can cause a ReqLeave on other Ports if this was the only Port */ /* maintaining this group for their Proxy Applicant. */ propagate_leave(group,p); } } propagate_leave(group,p) Group_record *group; Port p; { Port q, first_leave = First_port, last_leave = Last_port; Garp_machine qm; for (q = First_port; q <= Last_port; q++) /* check all */ { /* */ if (q == p) continue; /* other ports */ /* else */ /* looking for */ qm = group->gm[q]; /* */ /* Registrars that are */ if ((qm & (Greg_state ^ Greg_manual)) != Greg_out) /* */ { /* not Out whose */ if (port_state(q) == Forwarding) /* Port is Forwarding. */ { /* */ if (first_leave == last_leave) return; /* if we have found two */ /* else */ /* nothing to do, if one */ first_leave = last_leave = q; /* only its Applicant */ } /* will need attention. */ } } for (q = first_leave; q <= last_leave; q++) { if (q == p) continue; /* else */ qm = group->gm[q]; /* if Proxy Applicant is */ if ((qm & (Gapp_state ^ Gapp_manual) != Gapp_out) /* */ { /* not Out, */ qm = (qm & (X_gapp & (~Gm_send_join))) /* cancel any pending */ | Gapp_out | Gm_send_leave; /* join, make Out, and */ group->gm[q] = qm; /* send leave. */ } } /* end for(;;) */ }