L’Internet est un protocole sans état: les paquets sont traités puis oubliés par les routeurs. Si un routeur redémarre, il peut reprendre le traitement comme si de rien n’était, les flux sont soit interrompus soit dirigés vers d’autres routeurs pendant la panne.
Pour faire face à la pénurie d’adresses, le groupe Softwire a proposé des solutions dont une avec NAT dans le coeur du réseau. Les rapports de projet d’étudiants mis sur ce blog en montrent l’intérêt mais également les limitations et problèmes que créent la centralisation dans le réseau.
Rémi Despres (père de 6rd) tente un nouveau coup d’éclat en poussant 4rd (où le r veut dire residual deploiement à la place de Rémi Despres euh rapid deploiement). Cette solution est sans état, elle construit l’adresse IPv6 du tunnel en prenant des informations contenues dans les paquets IPv4 et les numéros de ports.
Le groupe Softwire a accepté du bout des lèvres ces solutions sans état.
Francis Dupont a fait quelques calculs de complexité entre les NAT centralisés (qu’il connait bien, vu qu’il a ecrit l’AFTR de l’ISC) et A+P général et la solution 4rd. Sur ce point, il n’y a pas photo.
Analysis of performance of 3 address sharing mechanisms: CGN, A+P and 4RD.
Im Memoriam: Philippe Flajolet
In all cases the hard case is to decide what to do with a packet received from the external/Internet-facing side. The other case can be split into two phases, the first based on where the packet comes from.
The first mechanism is the Carrier Grade NAT (CGN, as known as Large Scale NAT (LSN) too). The processing of a reassembled packet from the external side begins by the lookup of the corresponding mapping in a table containing all active mappings. This table can be implemented by a hash table (Linux kernel way), a search tree, …, (my AFTR code uses a RedBlack tree, known to be the best balanced tree algorithm in dynamic conditions and with a fixed per node space overhead for the tree
structure, and a dynamic sized simple hash table for caching). But with N for the number of active mappings, the complexity of the lookup which always takes at least the half of the running time
is O(log(N)). N bounded by the number of public address * the number of ports * the number of protocols. In detail the number of public address is a deployment parameter, it is at least one so you can implement a CGN by a farm of small boxes, each box in charge of one public address. The number of port is 2^16, the number of protocols is in theory 2^8 but in practice only a few (3: TCP, UDP and ICMP echo) values are of interest. To conclude it seems the big fat NAT should come with a big fat bill, and I have not considered hot standby or logging (required by laws in many countries) associated costs which likely follow the same scale.
The second mechanism is Address-plus-Port (A+P). I shan’t enter into the different variants: I keep the common one using an ingress filter extended from source address to address and port for reassembled
packets from the internal/customer-facing side, and a so-called port-range router (PRR) for reassembled packets from the external/Internet-facing side. A PRR works exactly like a standard IP router but in place of using the destination IP address as the key it uses the destination IP address, the protocol and the destination port, so its place is between IPv4 routers acting on 32 bits and IPv6 routers acting on 128 bits as it acts on 32 + 8 + 16 = 56 bits.
The number of bits matters only for the used space, for the performance the parameter is the number of routes. So with C for the number of clients and with a small number of port ranges per client and protocol, the complexity of the lookup is O(log(C)). By the way I believe the best known algorithm is the Patricia tree.
Two comments: this proves a PRR has the same complexity than the routing infrastructure between the ISP device and ISP customers, or with other words, to use a PRR or a standard router where
all customers are directly attached is equivalent. The NAT function is performed in the customers’ home gateways (HGW, as known as customer premises equipment/router, etc) so the addition of the PRR processing and the customer NAT processing is the same than for a CGN receiving a packet from the internal/customer side. But this could lead to a false trade-off: HGWs already provide the NAT function so to use it comes for free for the ISP.
The last mechanism is 4RD (RD officially stands for Residual Deployment) in its address sharing variant, so it works on reassembled (similar methods to get access to the port fields have the same requirements than reassembly) packets as any address sharing mechanisms. It is a pure algorithmic mechanism so the lookup is replaced by bit field manipulation. Its complexity is O(1), but one can argue
it is no longer the place where time is spent.