576
`
`Radix Tree Routing Tables
`
`Chapter 18
`
`61 #define rn_mask
`62 #define rn_off
`63 #define rn_l
`64 #define rn_r
`
`rn_u.rn_leaf.rn_Mask
`rn_u.rn_node.rn_Off
`rn_u.rn_node.rn_L
`rn_u.rn_node.rn_R
`
`radix.h
`
`Figure 18.18 radix_node structure: the nodes of the routing tree.
`
`41--45
`
`41--42
`
`43
`
`The first five members are common to both internal nodes and leaves, followed by a
`union defining three members if the node is a leaf, or a different three members if the
`node is internal. As is common throughout the Net/3 code, a set of #define state-
`ments provide shorthand names for the members in the union.
`rn_mkl i st is the head of a linked list of masks for this node. We describe this field
`in Section 18.9. rn_p points to the parent node.
`If rn_b is greater than or equal to 0, the node is an internal node, else the node is a
`leaf. For the internal nodes, rn_b is the bit number to test: for example, its value is 32
`in the top node of the tree in Figure 18.4. For leaves, rn_b is negative and its value is -1
`minus the index of the network mask. This index is the first bit number where a 0 occurs.
`Figure 18.19 shows the indexes of the masks from Figure 18.4.
`
`3333
`2345
`0000
`iiii
`iiii
`
`3333
`6789
`0000
`iiii
`iiii
`
`32~itIP mask ~its32-63)
`4444
`4444
`4455
`5555
`0123
`4567
`8901
`2345
`0000
`0000
`0000
`0000
`0000
`0000
`0000
`0000
`iiii
`iiii
`iiii
`iiii
`
`5555
`6789
`0000
`0000
`iii0
`
`6666
`0123
`0000
`0000
`O00O
`
`index
`
`rn_b
`
`0
`40
`59
`
`-1
`-41
`--60
`
`00000000:
`ff000000:
`ffffffe0:
`
`Figure 18.19 Example of mask indexes.
`
`As we can see, the index of the all-zero mask is handled specially: its index is 0, not 32.
`rn_bmask is a 1-byte mask used with the internal nodes to test whether the corre-
`sponding bit is on or off. Its value is 0 in leaves. We’ll see how this member is used
`with the rn_o f f member shortly.
`Figure 18.20 shows the three values for the rn_flags member.
`
`44
`
`45
`
`Description
`Constant
`RNF_ACTIVE this node is alive (for rt free)
`leaf contains normal route (not currently used)
`RN<_NORMAL
`leaf is a root leaf for the tree
`RNF ROOT
`
`Figure 18.20 rn_flags values.
`
`The RNF_ROOT flag is set only for the three radix nodes in the radix_node_head
`structure: the top of the tree and the left and right end nodes. These three nodes can
`never be deleted from the routing tree.
`
`DELL EX.1095.601
`
`

`

`Section 18.5
`
`Radix Node Data Structures 877
`
`48--49
`
`rn_key points to the socket address structure and rn_mask points to a
`For a leaf,
`socket address structure containing the mask. If rn_mask is null, the implied mask is
`all one bits (i.e., this route is to a host, not to a network).
`Figure 18.21 shows an example corresponding to the leaf for 140.252.13.32 in Fig-
`ure 18.4.
`
`to radix_node { }
`for bit 63
`
`-60
`
`sockaddr_in{}
`
`
`RNF ACTIVE 140.252. 13 . 32
`,116! 2! 0 I ol olo ! ol
`
` ? i? 5i ?i221
`
`o ]
`
`0
`
`radix_node{}
`-rn_mklist
`rn_p
`rn_b
`rn bmask
`rn_flags
`rn_key
`rn_mask
`rn_dupedkey
`
`radix_mask{}
`
`~ rm_off
`
`rm_unused
`rm_flags
`rm_mklist
`rm_mask
`rm_refs
`
`
`
`Fignre 18.21 radix_node structure corresponding to leaf for 140.252.13.32 in Figure 18.4.
`
`structure, which we describe in Fig-
`This example also shows a radix_mask
`ure 18.22. We draw this latter structure with a smaller width, to help distinguish it as a
`different structure from the radi×_node; we’ll encounter both structures in many of
`the figures that follow. We describe the reason for the radix_mask structure in Sec-
`tion 18.9.
`points to
`The rn_b of -60 corresponds to an index of 59.
`rn_key
`with a length of 16 and an address family of 2 (AF_INET). The mask structure pointed
`to by rn_mask and rm mask has a length of 8 and a family of 0 (this family is
`AF_UNSPEC, but it is never even looked at).
`The rn_dupedkey pointer is used when there are multiple leaves with the same
`key. We describe these in Section 18.9.
`We describe rn_off in Section 18.8. rn_l and rn_r are the left and right pointers
`for the internal node.
`Figure 18.22 shows the radix_mask structure.
`
`50-51
`
`52 58
`
`DELL EX.1095.602
`
`

`

`578
`
`Radix Tree Routing Tables
`
`Chapter 18
`
`76 extern struct radix_mask {
`/* bit offset; -l-index(netmask) */
`77
`short
`rm b;
`/* cf. rn_bmask */
`78
`char
`rm unused;
`/* cf. rn_flags */
`rm_flags;
`79
`u_char
`struct radix_mask *rm mklist; /* more masks to try */
`80
`81
`caddr_t rm mask;
`/* the mask */
`int
`rm_refs;
`/* # of references to this struct */
`82
`*rn_mkfreelist;
`83 }
`
`Figure 18.22 radix_mask structure.
`
`radix.h
`
`radix.h
`
`76--83
`
`Each of these structures contains a pointer to a mask: rm_mask, which is really a
`pointer to a socket address structure containing the mask. Each radix_node structure
`points to a linked list of radix_mask structures, allowing multiple masks per node:
`rn_mklist points
`to the first,
`rm_mklist points
`and then each
`to the next. This struc-
`
`ture definition also declares the global rn_mkfree i i st, which is the head of a linked
`list of available structures.
`
`18.6 Routing Structures
`
`The focal points of access to the kernel’s routing information are
`
`1.
`2.
`3.
`
`the rtalloc function, which searches for a route to a destination,
`the route structure that is filled in by this function, and
`the rtentry structure that is pointed to by the
`structure.
`route
`
`Figure 18.8 showed that the protocol control blocks (PCBs) used by UDP and TCP
`(Chapter 22) contain a route structure, which we show in Figure 18.23.
`
`46 struct route {
`47
`struct rtentry *ro_rt;
`48
`struct sockaddr ro_dst;
`49 };
`
`mute.h
`/* pointer to struct with information */
`/* destination of this route */
`
`mute.h
`
`Figure 18.23 route structure.
`
`ro_dst is declared as a generic socket address structure, but for the Internet protocols
`it is a sockaddr_in. Notice that unlike most references to this type of structure,
`ro_dst is the structure itself, not a pointer to one.
`At this point it is worth reviewing Figure 8.24, which shows the use of these routes
`every time an IP datagram is output.
`
`If the caller passes a pointer to a route structure, that structure is used. Other-
`wise a local route structure is used and it is set to 0, setting ro_rt to a null
`pointer. UDP and TCP pass a pointer to the route structure in their PCB to
`ip_output.
`
`DELL EX.1095.603
`
`

`

`Section 18.6
`
`Routing Structures
`
`579
`
`¯ If the
`structure points to an rtentry structure (the ro_rt pointer is
`route
`nonnull), and if the referenced interface is still up, and if the destination address
`in the route structure equals the destination address of the IP datagram, that
`route is used. Otherwise the socket address structure so_dst is filled in with
`the destination IP address and rtal loc is called to locate a route to that desti-
`nation. For a TCP connection the destination address of the datagram never
`changes from the destination address of the route, but a UDP application can
`send a datagram to a different destination with each sendto.
`If rtalloc returns a null pointer in ro_rt, a route was not found and
`ip_output returns an error.
`If the RTF_GATEWAY flag is set in the rtentry structure, the route is indirect
`(the G flag in Figure 18.2). The destination address (dst) for the interface output
`function becomes the IP address of the gateway, the rt_gateway member, not
`the destination address of the IP datagram.
`
`¯
`
`Figure 18.24 shows the r tent ry structure.
`
`83 struct rtentry {
`84 struct radix_node rt_nodes[2] ; /* a leaf and an internal node */
`85
`86
`87
`88
`89
`90
`91
`92
`93
`94
`95 };
`96 #define rt_key(r) ((struct sockaddr *) ((r)->rt_nodes->rn_key))
`97 #define rt_mask(r) ((struct sockaddr *) ((r)->rt_nodes->rn mask))
`
`struct sockaddr *rt_gateway;
`short
`rt_flags;
`/*
`short
`rt_refcnt;
`/*
`u_long
`rt_use;
`/*
`struct ifnet *rt_ifp;
`/*
`struct ifaddr *rt_ifa;
`/*
`struct sockaddr *rt_gerrmask;
`caddr_t rt_llinfo;
`/*
`struct rt_metrics rt_rmx; /*
`struct rtentry *rt_gwroute; /*
`
`/* value associated with rn_key */
`Figure 18.25 */
`#held references */
`raw #packets sent */
`interface to use */
`interface address to use */
`/* for generation of cloned routes */
`pointer to link level info cache */
`metrics: Figure 18.26 */
`implied entry for gatewayed routes */
`
`route.h
`
`route.h
`
`Figure 18.24 rtentry structure.
`
`83 84
`
`86
`
`85
`
`Two radix_node structures are contained within this structure. As we noted in
`the example with Figure 18.7, each time a new leaf is added to the routing tree a new
`internal node is also added, rt_nodes [0] contains the leaf entry and rt_nodes [1]
`contains the internal node. The two #define statements at the end of Figure 18.24 pro-
`vide a shorthand access to the key and mask of this leaf node.
`Figure 18.25 shows the various constants stored in rt_flags and the correspond-
`ing character output by n e t s t at in the "Flags" column (Figure 18.2).
`’ The RTF_BLACKHOLE flag is not output by netstat and the two with lowercase
`flag characters, RTF_DONE and RTF_MASI<, are used in routing messages and not nor-
`mally stored in the routing table entry.
`If the RTF_GATEWAY flag is set, rt_gateway contains a pointer to a socket address
`structure containing the address (e.g., the IP address) of that gateway. Also,
`
`DELL EX.1095.604
`
`

`

`580
`
`Radix Tree Routing Tables
`
`Chapter 18
`
`netstat
`flag
`
`Description
`
`discard packets without error (Ioopback driver: Figure 5.27)
`generate new routes on use (used by ARP)
`kernel confirmation that message from process was completed
`created dynamically (by redirect)
`destination is a gateway (indirect route)
`host entry (else network entry)
`set by ARP when rt_l 1 info pointer valid
`subnet mask present (not used)
`modified dynamically (by redirect)
`protocol-specific routing flag
`protocol-specific routing flag (ARP uses)
`discard packets with error (loopback driver: Figure 5.27)
`
`manually added entry (route program)
`route usable
`external daemon resolves name (used with X.25)
`
`cdDGHLmM12 RSU X
`
`Figure 18.25
`
`rt_flags values.
`
`Constant
`
`RTF_BLACKHOLE
`RTF_CLONING
`RTF_DONE
`RTF_DYNAMIC
`R TF_GA TEWA Y
`RTF_HOST
`
`RTF_LLINFO
`RTF_MASK
`R TF_MODIFIBD
`RTF PROTOI
`RTF_PROT02
`R TF_REJECT
`RTF_STATIC
`RTF_UP
`
`RTF_XRESOLVE
`
`rtentry for that gateway. This latter pointer was used in
`
`counter
`
`87
`
`89--90
`
`rt_gwroute points to the
`ether_output (Figure 4.15).
`rt_refcnt counts the "held" references to this structure. We describe this
`at the end of Section 19.3. This counter is output as the "Refs" column in Figure 18.2.
`rt_use is initialized to 0 when the structure is allocated; we saw it incremented in
`Figure 8.24 each time an IP datagram was output using the route. This counter is also
`the value printed in the "Use" column in Figure 18.2.
`rt_i fp and rt_i fa point to the interface structure and the interface address struc-
`ture, respectively. Recall from Figure 6.5 that a given interface can have multiple
`addresses, so minimally the r t_i f a is required.
`The rt_!linfo pointer allows link-layer protocols to store pointers to their proto-
`col-specific structures in the routing table entry. This pointer is normally used with the
`RTF_LLINFO flag. Figure 21.1 shows how ARP uses this pointer.
`
`54 struct rt_metrics {
`u_long rmx_locks;
`55
`u_long rmx mtu;
`56
`57
`u_long rmx_hopcount;
`u_long
`rmx_expire;
`58
`u_long
`rmx_recvpipe;
`59
`u_long
`rmx_sendpipe;
`60
`u_long
`61
`rmx_ssthresh;
`u_long
`62
`rmx_rtt;
`u_long
`rmx_rttvar;
`63
`u_long rmx_pksent;
`64
`65 ) ;
`
`route.h
`
`/* bitmask for values kernel leaves alone */
`/* MTU for this path */
`/* max hops expected */
`/* lifetime for route, e.g. redirect */
`/* inbound delay-bandwith product */
`/* outbound delay-bandwith product */
`/* outbound gateway buffer limit */
`/* estimated round trip time */
`/* estimated RTT variance */
`/* #packets sent using this route */
`
`~o~te.h
`
`Figure 18.26 rt_metrics structure.
`
`DELL EX.1095.605
`
`

`

`Section18.7
`
`Initialization: route_init and rtable_init Functions 581
`
`93
`
`54-65
`
`Figure 18.26 shows the rt_metrics structure, which is contained within the
`rtentry structure. Figure 27.3 shows that TCP uses six members in this structure.
`rmx_loeks is a bitmask telling the kernel which of the eight metrics that follow
`must not be modified. The values for this bitmask are shown in Figure 20.13.
`rmx_expire is used by ARP (Chapter 21) as a timer for each ARP entry. Contrary
`to the comment with rmx_expire, it is not used for redirects.
`
`Figure 18.28 summarizes the structures that we’ve described, their relationships,
`and the various types of socket address structures they reference. The rtentry that we
`show is for the route to 128.32.33.5 in Figure 18.2. The other radix_node contained in
`the rtentry is for the bit 36 test right above this node in Figure 18.4. The two
`sockaddr_dl structures pointed to by the first ifaddr were shown in Figure 3.38.
`Also note from Figure 6.5 that the ifnet structure is contained within an le_softc
`structure, and the second i faddr structure is contained within an in_ifaddr struc-
`ture.
`
`
`
`
`
`18.7 Initialization: route_init and rtable_init Functions
`
`The initialization of the routing tables is somewhat obscure and takes us back to the
`domain structures in Chapter 7. Before outlining the function calls, Figure 18.27 shows
`the relevant fields from the domain structure (Figure 7.5) for various protocol families.
`
`Unix
`value
`A F_ U!VkX
`
`XNS
`value
`AF_NS
`
`Comment
`
`in bits
`in bytes
`
`0r
`
`n inithead
`16
`16
`
`0000
`
`Routing
`value
`PF_ROUTE
`route_init
`
`000
`
`OSI
`value
`AF_ISO
`
`Internet
`value
`AF_INET
`
`0r
`
`n_inithead
`32
`16
`
`0r
`
`n inithead
`48
`32
`
`Member
`
`dom_family
`dom_init
`dom_rtattach
`dom_rtoffset
`dom maxrtkey
`
`Figure 18.27 Members of domain structure relevant to routing.
`
`The PF_ROUTE domain is the only one with an initialization function. Also, only the
`domains that require a routing table have a dom_rtattach function, and it is always
`rn_inithead. The routing domain and the Unix domain protocols do not require a
`routing table.
`The dom_rtoffset member is the offset, in bits, (from the beginning of the
`domain’s socket address structure) of the first bit to be examined for routing. The size
`of this structure in bytes is given by dom_maxrtkey. We saw earlier in this chapter that
`the offset of the IP address in the sockaddr_in structure is 32 bits. The
`dora maxrtkey member is the size in bytes of the protocol’s socket address structure:
`16 for sockaddr_in.
`Figure 18.29 outlines the steps involved in initializing the routing tables.
`
`DELL EX.1095.606
`
`

`

`582
`
`Radix Tree Routing Tables
`
`Chapter 18
`
`inpcb { }
`
`ro rt
`16 2 0
`80 20 21 05
`0
`
`] ]
`
`0
`
`0
`
`128.32.33. 5
`
`140.252.13.33
`
`both sockaddr_in{ }
`
`ifnet{}
`if_name
`if_next
`if_addrlist
`
`~le\O
`-~to SLIP ifnet{}
`
`1 0
`
`if_index
`if_unit
`
`i,~ Ethemetaddr ~
`1 l e I0
`
`~L20118! 1 1181316 101Io8!ool2olo31f61421 o !
`
`both sockaddr_dl { }
`
`o o 0
`
`~ 1612 ! 0 !Sclfc10d123!
`
`140.252.13.35
`
`140.252.13.63
`
`255.255.255.224
`
`
`
`all three sockaddr_in{ }
`
`ifaddr{}
`ifa_addr
`ifa_dstaddr
`ifa_netmask
`ifa_ifp
`ifa_next
`ifa rtrequest
`ifa_flags
`ifa_refcnt
`ifa_metric
`
`ifaddr{}
`ifa_addr
`ifa_brdaddr
`ifa netmask
`ifa_ifp
`ifa_next
`ifa_rtrequest
`ifa_flags
`ifa_refcnt
`ifa_metric
`
`Figure 18.28 Summary of routing structures.
`
`rtentry{}
`rn_mklist
`
`rn_b
`rn_bmask
`rn_flags
`rn_key
`rn_mask
`rn_dupedkey
`rn_mklist
`rn_p
`rn_b
`rn_bmask
`rn_flags
`rn_off
`rn_l
`
`rt_gateway
`rt_flags
`rt_refcnt
`rt_use
`rt_ifp
`rt_ifa
`rt_genmask
`rt_llinfo
`rmx_locks
`
`rmx_expire
`rmx_recvpipe
`rmx_sendpipe
`rmx_ssthresh
`rmx_rtt
`
`rmx_pksent
`rt_gwroute -
`
`radix_node{}
`for140.252.13.33
`
`DELL EX.1095.607
`
`

`

`Section18.7
`
`Initialization:
`route_init
`
`and
`rtable_init
`
`Functions
`
`583
`
`/* kernel initialization */
`
`main
`{
`
`.oo
`ifinit () ;
`
`();
`
`};.d.o.ma i hi_ n i t
`
`domaininit ( )
`{
`
`/* Figure 7.15 */
`
`ADDDOMAIN(unix);
`ADDDOMAIN(route);
`ADDDOHAIN(inet);
`ADDDOMAIN(osi);
`.oo
`for (dp : all domains ) {
`
`
`domain)
`-- ~ ~ ~P~(>.P~m-_=>~alnrlipt~°)nt~ctil~ ~: this
`
`//.~_~-rn init();
`
`rt~ble_init();
`
`1 ~n_init ( )
`for ( dp = all domains
`)
`if (dp->dom_maxrtkey > max_keylen)
`max_keylen : dp->dom_maxrtkey;
`
`allocate and initialize rn_zeros, rn_ones, masked_key ;
`
`~ rn_inithead(&mask_rnhead); /* allocate and init tree for masks */
`
`rtable_init()
`.
`for (dp : all domains )
`
`~ ./../~. ~ (*dp >dom_rtattach)(&rt_tables[dp->dom_family]);
`rn_inithead() /* dom_attach() function for all protocol families */
`
`
`
`allocate and initialize one radix_node_head structure;
`
`Figure 18.29 Steps involved in initialization of routing tables.
`
`DELL EX.1095.608
`
`

`

`584
`
`Radix Tree Routing Tables
`
`Chapter 18
`
`domaininit is called once by the kernel’s function when the system is ini-
`
`main
`tialized. The linked list of domain structures is built by the AD~)DOMAIN macro and the
`linked list is traversed, calling each domain’s dom_init function, if defined. As we
`saw in Figure 18.27, the only dom_init function is route_init, which is shown in
`Figure 18.30.
`
`49 void
`50 route_init ()
`51 {
`52
`
`rn_init(); /* initialize all zeros, all ones, mask table */
`
`53
`54 }
`
`rtable_init((void **) rt_tables);
`
`Figure 18.30 route_±nit function.
`
`route.c
`
`route.c
`
`The function rn_init, shown in Figure 18.32, is called only once.
`The function rtable_init, shown in Figure 18.31, is also called only once. It in
`turn calls all the dom_rtattach functions, which initialize a routing table tree for that
`domain.
`
`39 void
`40 rtable_init(table)
`41 void **table;
`42 {
`43
`44
`45
`46
`47
`48 }
`
`struct domain *dom;
`for (dom : domains; dom; dom = dom->dom_next)
`if (dom->dom_rtattach)
`dom->dom_rtattach(&table[dom->dom_family],
`dom->dom rtoffset);
`
`route.c
`
`route.c
`
`Figure 18.31 rtable_init
`
`function: call each domain’s
`dom_rtattach
`
`function.
`
`We saw in Figure 18.27 that the only
`which we describe in the next section.
`
`dom_rtattach
`
`function is
`
`18.8
`
`Initialization: rn_init
`
`and
`rn_±nithead
`
`Functions
`
`The function rn_init, shown in Figure 18.32, is called once by
`ize some of the globals used by the radix functions.
`
`750 void
`751 rn_init ( )
`752 {
`753
`754
`
`char *cp, *cplim;
`struct domain *dom;
`
`route_init
`
`radix.c
`
`DELL EX.1095.609
`
`

`

`Section18.8
`
`Initialization:
`rn_init
`
`and
`rn_inithead
`
`Functions 585
`
`for (dom - domains; dom; dom = dom->dom_next)
`if (dom->dom_maxrtkey > max_keylen)
`max_keylen = dom->dom maxrtkey;
`if (max_keylen -_ 0) {
`printf("rn_init: radix functions require max_keylen be set\n");
`Eeturn;
`
`]R
`
` Malloc(rn_zeros, char *, 3 * max_keylen);
`if (rn_zeros -- NULL)
`panic("rn_init");
`Bzero(rn_zeros, 3 * max_keylen);
`rn_ones cp : rn_zeros + max_keylen;
`maskedKey - cplim - rn_ones + max_keylen;
`while (cp < cplim)
`¯Cp++ : -i;
`
`if (rn_inithead((void **) &mask_rnhead, 0) == 0)
`panic("rn_init 2");
`
`Figure 18.32 rn_init function.
`
`radix.c
`
`755
`756
`757
`758
`759
`760
`761
`762
`763
`764
`765
`766
`767
`768
`769
`
`770
`771
`772
`
`750--761
`
`762--769
`
`Determine max_keylen
`
`All the domain structures are examined and the global is set to the
`max_keylen
`largest value of dom maxrtkey. In Figure ]8.27 the largest value is 32 for AF_ISO, but
`in a typical system that excludes the OSI and XNS protocols, max_keylen is ]6, the size
`of a sockaddr_in structure.
`
`Allocate and initialize rn_zeros, and
`
`rn_ones, maskedKey
`is allocated and the pointer stored in
`A buffer three times the size of
`max_keylen
`the global rn_zeros. R_Malloc is a macro that calls the kernel’s malloc function,
`specifying a type of M_RTABLE and M_DONTWAIT. We’ll also encounter the macros
`Bcmp, Bcopy, I3zero, and Free, which call kernel functions of similar names, with the
`arguments appropriately type cast.
`This buffer is divided into three pieces, and each piece is initialized as shown in Fig-
`ure 18.33.
`
`
`~ max_keylen bytes ~!~ raax_keylen bytes ~ bytes
`raax_keylen
`
`10 0 0 ... 0 0 0[i i i ... i 1 110 0 0
`
`...
`
`0 0 01
`
`rn_zeros
`
`rn_ones
`
`maskedKey
`
`Figure 18.33 rn_zeros, rn_ones, and raaskedKey arrays.
`
`is an array of all one bits, and
`is an array of all zero bits, rn_ones
`rn_zeros
`maskedKey is an array used to hold a temporary copy of a search key that has been
`masked.
`
`DELL EX.1095.610
`
`

`

`586
`
`Radix Tree Routing Tables
`
`Chapter 18
`
`770--772
`
`Initialize tree of masks
`The function rn_inithead is called to initialize the head of the routing tree for the
`address masks; the rad±×_node_head structure pointed to by the global
`raask_rnhead in Figure 18.8.
`From Figure 18.27 we see that rn_in±¢head is also the dom_a¢¢ach function for
`all the protocols that require a routing table. Instead of showing the source code for this
`function, Figure 18.34 shows the radix_node_head structure that it builds for the
`Internet protocols.
`
`radix_node { }
`rnh_nodes [ 0 ]
`(leftmost leaf)
`
`radix node{}
`rnh_nodes[1]
`(internalnode)
`top oftree
`
`radix_node{}
`rnh_nodes[2]
`(rightmostleaf)
`
`0 0 r
`
`n_a ddrou t e
`NULL
`rn delroute
`NULL
`re_match
`NULL
`rn_walktree
`NULL
`
`-33
`
`0 A
`
`CTIVE I ROOT
`rn zeros
`NULL
`NULL
`NULL
`
`32
`OxSO
`ACTIVE I ROOT
`4
`
`~ULL
`
`-33
`
`0 A
`
`CTIVE I ROOT
`rn_olqes
`NULL
`NULL
`
`radix_node_head { }
`rnh_treetop
`rnh_addrsize
`rnh_pktsize
`rnh_addaddr
`rnh_addpkt
`rnh_deladdr
`rnh_delpkt
`rnh_matchaddr
`rnh_matchpkt
`rnh_walktree
`rn mklist
`rn_p
`rn b
`rn_bmask
`rn_flags
`rn_key
`rn_mask
`rn_dupedkey
`rn_mklist
`rn_p
`rn_b
`rn_bmask
`rn_flags
`rn_off
`rn_l
`rn_r
`rn mklist
`rn_p
`rn_b
`rn_bmask
`rn_flags
`rn_key
`rn_mask
`rn_dupedkey
`
`rt_tables [ ] :
`
`01
`
`AF_INET = 2
`3
`
`25
`
`Figure 18.34 radix_node_head structure built by rn_inithead for Internet protocols.
`
`The three radix_node structures form a tree: the middle of the three is the top (it is
`pointed to by rnh_treetop), the first of the three is the leftmost leaf of the tree, and
`
`DELL EX.1095.611
`
`

`

`Section 18.9
`
`Duplicate Keys and Mask Lists
`
`587
`
`the last of the three is the rightmost leaf of the tree. The parent pointer of all three
`nodes (rn_p) points to the middle node.
`rn_b is the bit position to test. It is from the
`The value 32 for rnh_nodes [ 1 ] .
`dom_rtoffset member of the Internet domain structure (Figure 18.27). Instead of
`performing shifts and masks during forwarding, the byte offset and corresponding byte
`mask are precomputed. The byte offset from the start of a socket address structure is in
`the rn_off member of the radix_node structure (4 in this case) and the byte mask is
`in the rn_bmask member (0x8 0 in this case). These values are computed whenever a
`radix_node structure is added to the tree, to speed up the comparisons during for-
`warding. As additional examples, the offset and byte mask for the two nodes that test
`bit 33 in Figure 18.4 would be 4 and 0x4 0, respectively. The offset and byte mask for
`the two nodes that test bit 63 would be 7 and 0x01.
`The value of -33 for the rn_b member of both leaves is negative one minus the
`index of the leaf.
`The key of the leftmost node is all zero bits (rn_zeros) and the key of the right-
`most node is all one bits (rn_ones).
`All three nodes have the IRNF_ROOT flag set. (We have omitted the RNF_ prefix.)
`This indicates that the node is one of the three original nodes used to build the tree.
`These are the only nodes with this flag.
`
`One detail we have not mentioned is that the Network File System (NFS) also ~ses the routing
`table functions. For each mount point on the local host a radix_node_head structure is allo-
`cated, along with an array of pointers to these structures (indexed by the protocol family), sim-
`ilar to the rt_tables array. Each time this mount point is exported, the protocol address of
`the host that can mount this filesystem is added to the appropriate tree for the mount point.
`
`18.9 Duplicate Keys and Mask Lists
`
`Before looking at the source code that looks up entries in a routing table we need to
`understand two fields in the radix_node structure: rn_dupedkey, which forms a
`linked list of additional radix_node structures containing duplicate keys, and
`r n_mkl i s t, which starts a linked list of radix_mask structures containing network
`masks.
`We first return to Figure 18.4 and the two boxes on the far left of the tree labeled
`"end" and "’default." These are duplicate keys. The leftmost node with the RNF_ROOT
`flag set (rnh_nodes [0] in Figure 18.34) has a key of all zero bits, but this is the same
`key as the default route. We would have the same problem with the rightmost end
`node in the tree, which has a key of all one bits, if an entry were created for
`255.255.255.255, but this is the limited broadcast address, which doesn’t appear in the
`routing table. In general, the radix node functions in Net/3 allow any key to be dupli-
`cated, if each occurrence has a unique mask.
`Figure 18.35 shows the two nodes with a duplicate key of all zero bits, In this figure
`we have removed the RNF_ prefix for the rn_flags and omit nonnull parent, left, and
`right pointers, which add nothing to the discussion.
`
`DELL EX.1095.612
`
`

`

`888
`
`Radix Tree Routing Tables
`
`Chapter 18
`
`radix node{}
`rn_mklist
`rn_p
`rn b
`rn_bmask
`rn_flags
`rn_off
`rn_left
`rn_right
`
`}
`
`NULL
`
`32
`Ox80
`ACTIVEIROOT
`4
`
`head of routing tree:
`node for bit 32 at
`top of Figure 18.4
`
`o I
`
`33
`
`o A
`
`CTIVE I ROOT
`
`NULL
`
`rn_zeros:
`
`left pointer
`from bit 33
`node
`
`radix_node{
`
`rn_p
`rn_b
`rn_bmask
`rn_flags
`
`Ir n_mklist
`
`rn_mask
`rn_dupedkey
`
`0.0.0.0
`~16[ 2 ] 0 100100!00[00[
`
`0
`
`[
`
`sockaddr_in
`
`-i
`
`0 A
`
`CTIVE ~
`
`.~
`
`NULL
`
`ULL
`
`radix_node{}
`rn_mklist
`
`rn b
`rn bmask
`rn_flags
`rn_key
`rn_mask
`rn_dupedkey
`
`radix_mask{}
`rm_off
`rm_unused
`rm flags
`rm mklist
`rm_mask
`rm_refs
`
`Figure 18.35 Duplicated nodes with a key of all zero bits.
`
`The top node is the top of the routing tree--the node for bit 32 at the top of Fig-
`ure 18.4. The next two nodes are leaves (their rn_b values are negative) with the
`rn_dupedkey member of the first pointing to the second. The first of these two leaves
`is the rnh_nodes [0] structure from Figure 18.34, which is the left end marker of the
`tree--its RNF_ROOT flag is set. Its key was explicitly set by rn_inithead to
`rn_zeros.
`The second of these leaves is the entry for the default route. Its rn_key points to a
`sockaddr_in with the value 0.0.0.0, and it has a mask of all zero bits. Its rn_mask
`points to rn_zeros, since equivalent masks in the mask table are shared.
`
`DELL EX.1095.613
`
`

`

`Section 18.9
`
`Duplicate Keys and Mask Lists 589
`
`Normally keys are not shared, let alone shared with masks. The rn key pointers of the two
`end markers (those with the RNF_ROOT flag) are special since they are built by rm_inithead
`(Figure 18.34). The key of the left end marker points to rn_zeros and the key of the right end
`marker points to rn_ones.
`
`The final structure is a radix_mask structure and is pointed to by both the top
`mode of the tree and the leaf for the default route. The list from the top node of the tree
`is used with the backtracking algorithm when the search is looking for a network mask.
`The list of radix_mask structures with an internal node specifies the masks that apply
`to subtrees starting at that node. In the case of duplicate keys, a mask list also appears
`with the leaves, as we’ll see in the following example.
`We now show a duplicate key that is added to the routing tree intentionally and the
`resulting mask list. In Figure 18.4 we have a host route for 127.0.0.1 and a network
`route for 127.0.0.0. The default mask for the class A network route is 0xf f 000000, as
`we show in the figure. If we divide the 24 bits following the class A network ID into a
`16-bit subnet ID and an 8-bit host ID, we can add a route for the subnet 127.0.0 with a
`mask of OxffffffO0:
`
`bsdi $ route add 127.0.0.0 -netmask OxffffffO0 140.252,13.33
`
`Although it makes little practical sense to use network 127 in this fashion, our interest is
`in the resulting routing table structure. Although duplicate keys are not common with
`the Internet protocols (other than the previous example with the default route), dupli-
`cate keys are required to provide routes to subnet 0 of any network.
`There is an implied priority in these three entries with a network ID of 127. If the
`search key is 127.0.0.1 it matches all three entries, but the host route is selected because
`it is the most specific: its mask (0xffffffff) has the most one bits. If the search key is
`127.0.0.2 it matches both network routes, but the route for subnet 0, with a mask of
`0×££££££00, is more specific than the route with a mask of 0×ff000000. The search
`key 127.1.2.3 matches only the entry with a mask of 0 x f f 0000 00.
`Figure 18.36 shows the resulting tree structure, starting at the internal node for bit
`33 from Figure 18.4. We show two boxes for the entry with the key of 127.0.0.0 since
`there are two leaves with this duplicate key.
`
`OxO0000000
`
`~
`
`~
`
`127.0.0.0
`OxffffffO0
`OxffO00000
`
`~
`
`127~A
`
`Figure 18.36 Routing tree showing duplicate keys for 127.0.0.0.
`
`DELL EX.1095.614
`
`

`

`590
`
`Radix Tree Routing Tables
`
`Chapter 18
`
`Figure 18.37 shows the resulting
`
`radix_node and radix_mask
`
`structures.
`
`radix_node{}
`rn_mklist
`rn_p
`rn b
`rn bmask
`rn_flags
`rn_off
`rn_left
`rn_right
`
`63
`OxOl
`ACTIVE
`7
`
`node for bit 63
`
`radix_node{ } for 127.0.0.1
`
`sockaddr_in
`127. 0 . 0 . 0
`
`17flooloolool
`
`sockaddr_in
`127. 0 . 0 . 0
`
`~a61 2I o 17 1ooloolool
`
`5101010 If looloolool
`
`0
`
`0
`
`o
`
`57
`
`0A
`
`CTIVE
`
`-41
`
`0A
`
`CTIVE
`
`41
`
`~ULL
`
`radix node{}
`
`l r n_mklist
`
`rn_p
`rn_b
`rn bmask
`rn_flags
`rn_key
`rn_mask
`rn_dupedkey
`
`radix_node{}
`~-~ -
`~ rn mklist
`rn_p
`rn b
`rn_bmask
`rn_ f iag s
`rn_key
`rn mask
`rn_dupedkey
`
`radix_mask { }
`
`rm_unused
`rm_flags
`rm_mklist
`rm_mask
`rm_refs
`
`radix_mask{}
`
`~ rm_off
`
`rm_unused
`rm_flags
`rm_mklist
`rm_mask
`rm_refs
`
`Figure 18.37 Example routing table structures for the duplicate keys for network 127.0.0.0.
`
`DELL EX.1095.615
`
`

`

`Section 18.10
`
`rn_match Function 591
`
`structures for each radix_node. The mask
`First look at the linked list of
`radix_mask
`list for the top node (bit 63) consists of the entry for 0xffffff00 followed by
`0xf f 0 0 0 0 0 0. The more-specific mask comes first in the list so that it is tried first. The
`mask list for the second radix_node (the one with the rn_b of -57) is the same as that
`of the first. But the list for the third radix_node consists of only the entry with a mask
`of OxffO00000.
`Notice that masks with the same value are shared but keys with the same value are
`not. This is because the masks are maintained in their own routing tree, explicitly to be
`shared, because equal masks are so common (e.g., every class C network route has the
`same mask of 0 x f f f f f f 00), while equal keys are infrequent.
`
`18.10 rn_mat ch Function
`
`function, which is called as the rnh_matchaddr function
`We now show the
`rn_match
`for the Internet protocols. We’ll see that it is called by the r t a 1 ! o c 1 function, which is
`called by the rtal loc function. The algorithm is as follows:
`
`1. Start at the top of the tree and go to the leaf corresponding to the bits in the
`search key. Check the leaf for an exact match (Figure 18.38).
`2. Check the leaf for a network match (Figure 18.40).
`3. Backtrack (Figure 18.43).
`
`Figure 18.38 shows the first part of rn_match.
`
`135 struct radix_node *
`136 rn_match(v_arg, head)
`137 void *v_arg;
`138 struct radix_node_head *head;
`139 {
`140
`141
`142
`143
`144
`145
`
`caddr_t v : v_arg;
`struct radix_node *t head->rnh_treetop, *x;
`caddr_t cp = v, cp2, cp3;
`caddr_t cplim, mstart;
`struct radix_node *saved_t, *top = t;
`off - t->rn_off, vlen - *(u_char *) cp, matched_off;
`int
`
`radix.c
`
`146
`147
`148
`149
`150
`151
`152
`153
`154
`155
`
`* Open code rn_search(v, top) to avoid overhead of extra
`* subroutine call.
`*/
`for (; t->rn_b >: 0;) {
`if (t->rn_bmask & cp[t->rn_off])
`t = t->rn_r; /* right if bit on */
`
`else
`t : t->rn_l;
`
`/* left if bit off */
`
`DELL EX.1095.616
`
`

`

`592
`
`Radix Tree Routing Tables
`
`Chapter 18
`
`156
`157
`158
`159
`160
`161
`162
`163
`164
`165
`166
`167
`168
`169
`170
`171
`172
`
`/*
`* See if we match exactly as a host destination
`*/
`cp +: off;
`cp2 = t->rn_key + off;
`cplim = v + vlen;
`for (; cp < cplim; cp++, cp2++)
`if (*cp !: *cp2)
`goto onl;
`
`/*
`* This extra grot is in case we are explicitly asked
`~ to look up the default, ugh!
`*/
`if ((t->rn_flags & RNF_ROOT) && t->rn_dupedkey)
`t : t->rn._dupedkey;
`return t;
`onl:
`
`radix.c
`
`Figure 18.38 rn_mat ch function: go down tree, check for exact host match.
`
`135--145
`
`146--155
`
`156--164
`
`The first argument v_arg is a pointer to a socket address structure, and the second
`
`argument head is a pointer to the rad±x_node_head structure for the protocol. All
`protocols call this function (Figure 18.17) but each calls it with a different head argu-
`ment.
`In the assignment statements, o £ f is the rn_o f f member of the top node of the tree
`(4 for Internet addresses, from Figure 18.34), and vlen is the length field from the
`socket address structure of the search key (16 for Internet addresses).
`Go down the tree to the corresponding leaf
`This loop starts at the top of the tree and moves down the left and right branches
`until a leaf is encountered (rn_b is less than 0). Each test of the appropriate bit is made
`using the precomputed byte mask in rn_bmask and the corresponding precomputed
`offset in rn_off. For Internet addresses,
`rn_of f will be 4, 5, 6, or 7.
`Check for exact match
`When the leaf is encountered, a check is first made for an exac