rfc2123.txt

<VC++网络游戏建摸与实现>源代码

   In the PC environment a variety of 'generalised' network interfaces
   are available.  I considered those available from companies such as
   Novell, DEC and Microsoft and decided against them, partly because
   they are proprietary, and partly because they did not appear to be
   particularly easy to use.  Instead I chose the CRYNWR Packet Drivers
   [3] .  These are available for a wide variety of interface cards and
   are simple and clearly documented.  They support Ethernet's
   promiscuous mode, allowing one to observe headers for every passing
   packet in a straightforward manner.  One disadvantage of the Packet
   Drivers is that it is harder to use them with newer user shells (such
   as Microsoft Windows), but this was irrelevant since I intended to
   run the meter as the only program on a dedicated machine.

   Timing on the PC presented a challenge since the BIOS timer routines
   only provide a clock tick about 18 times each second, which limits
   the available time resolution.  Initially I made do with a timing
   resolution of one second for packets, since I believed that most
   flows existed for many seconds.  In recent years it has become
   apparent that many flows have lifetimes well under a second.  To
   measure them properly with the Traffic Flow Meter one needs times
   resolved to 10 millisecond intervals, this being the size of
   TimeTicks, the most common time unit within SNMP [4].  Since all the
   details of the original PC are readily available [5], it was not
   difficult to understand the underlying hardware.  I have written PC
   timer routines for NeTraMet which read the hardware timer with 256
   times the resolution of the DOS clock ticks, i.e. about 5 ticks per
   millisecond.

   There are many TCP/IP implementations available for DOS, but most of
   them are commercial software.  Instead I chose Waterloo TCP [6],
   since this was available (including full source code) as public
   domain software.  This was necessary since I needed to modify it to
   allow me to save incoming packet headers at the same time as
   forwarding packets destined for the meter to the IP handler routines.
   For SNMP I chose CMU SNMP [7], since again this was available (with
   full source code) as public domain software.  This made it fairly
   simple to port it from Unix to the PC.





Brownlee                     Informational                      [Page 6]

RFC 2123                Traffic Flow Measurement              March 1997


   Finally, for the NeTraMet development I used Borland's Turbo C and
   Turbo Assembler.  Although many newer C programming environments are
   now available, I have been perfectly happy with Turbo C version 2 for
   the NeTraMet project!

2.2.2 Unix environment

   In implementing the Unix meter, the one obvious problem was 'how do I
   get access to packet headers?'  Early versions of the Unix meter were
   implemented using various system-specific interfaces on a SunOS 4.2
   system.  Later versions use libpcap [8], which provides a portable
   method of obtaining access to packet headers on a wide range of Unix
   systems.  I have verified that this works very well for ethernet
   interfaces on Solaris, SunOS, Irix, DEC Unix and Linux, and for FDDI
   interfaces on Solaris.  libpcap provides timestamps for each packet
   header with resolution determined by the system clock, which is
   certainly better than 10 ms!

   All Unix systems provide TCP/IP capabilities, so that was not an
   issue.  For SNMP I used CMU SNMP, exactly as on the PC.

2.3 Implementing the meter

   This section briefly discusses the data structures used by the meter,
   and the packet matching process.  One very strong concern during the
   evolution of NeTraMet has been the need for the highest possible
   level of meter performance.  A variety of interesting optimisations
   have been developed to achieve this; as discussed below.  Another
   particular concern was the need for efficient and effective memory
   managent; this is discussed in detail below.

2.3.1 Data structures

   All the programs in NeTraMet, NeMaC and their supporting utility
   programs are written in C, partly because C and its run-time
   libraries provides good access to the underlying hardware, and partly
   because I have found it to be a highly portable language.














Brownlee                     Informational                      [Page 7]

RFC 2123                Traffic Flow Measurement              March 1997


   The data for each flow is stored in a C structure.  The structure
   includes all the flow's attribute values (including packet and byte
   counts), together with a link field which can be used to link flows
   into lists.  NeTraMet assumes that Adjacent addresses are 802 MAC
   Addresses, which are all six bytes long.  Similarly, Transport
   addresses are assumes to be two bytes long, which is the case for
   port numbers in IP.  Peer addresses are normally four bytes or less
   in length.  They may, however, be as long as 20 bytes (for CLNS). I
   have chosen to use a fixed Peer address size, defined at compile
   time, so as to avoid the complexity of having variable-sized flow
   structures.

   The flow table itself is an array of pointers to flow data
   structures, which allows indexed access to flows via their flow
   numbers.  There is also a single large hash table, referred to in the
   Architecture document [1] as the flow table's 'search index'.  Each
   hash value in the table points to a circular chain of flows.  To find
   a flow one computes its hash value then searches that value's flow
   chain.

   The meter stores each rule in a C structure.  All the rule components
   have fixed sizes, but address fields must be wide enough to hold any
   type of address - Adjacent, Peer or Transport.  The rule address
   width is defined at compile time, in the same way as flow Peer
   addresses.  Each rule set is implemented as an array of pointers to
   rule data structures, and the rule table is an array of pointers to
   the rule sets.  The size of each rule set is specified by NeMaC
   (before it begins downloading the rule set), but the maximum number
   of rule sets is defined at compile time.

2.3.2 Packet matching

   Packet matching is carried out in NeTraMet exactly as described in
   the Architecture document [1].  Each incoming packet header is
   analysed so as to determine its attribute values.  These values are
   stored in a structure which is passed to the Packet Matching Engine.
   To facilitate matching with source and destination reversed this
   structure contains two substructures, one containing the source
   Adjacent, Peer and Transport address values, the other containing the
   destination address values.

2.3.3 Testing groups of rule addresses

   As described in the Architecture [1] each rule's address will usually
   be tested, i.e. ANDed with the rule's mask and compared with the
   rule's value.  If the comparison fails, the next rule in sequence is
   executed.  This allows one to write rule sets which use a group of
   rules to test an incoming packet to see whether one of its addresses



Brownlee                     Informational                      [Page 8]

RFC 2123                Traffic Flow Measurement              March 1997


   - e.g. its SourcePeerAddress - is one of a set of specified IP
   addresses.  Such groups of related rules can grow quite large,
   containing hundreds of rules.  It was clear that sequential execution
   of such groups of rules would be slow, and that something better was
   essential.

   The optimisation implemented in NeTraMet is to find groups of rules
   which test the same attribute with the same mask, and convert them
   into a single hashed search of their values.  The overhead of setting
   up hash tables (one for each group) is incurred once, just before the
   meter starts running a new rule set.  When a 'group' test is to be
   performed, the meter ANDs the incoming attribute value, computes a
   hash value from it, and uses this to search the group's hash table.
   Early tests showed that the rule hash chains were usually very short,
   usually having only one or two members.  The effect is to reduce
   large sequences of tests to a hash computation and lookup, with a
   very small number of compares; in short this is an essential
   optimisation for any traffic meter!

   There is, of course, overhead associated with performing the hashed
   compare.  NeTraMet handles this by having a minimum group size
   defined at compile time.  If the group is too small it is not
   combined into a hashed group.

   In early versions of NeTraMet I did not allow Gotos into a hashed
   group of rules, which proved to be an unnecessarily conservative
   position.  NeTraMet stores each group's hash table in a separate
   memory area, and keeps a pointer to the hash table in the first rule
   of the group.  (The rules data structure has an extra component to
   hold this hash table pointer).  Rules within the group don't have
   hash table pointers; when they are executed as the target of a Goto
   rule they behave as ordinary rules, i.e. their tests are performed
   normally.

2.3.4 Compression of address masks

   When the Packet Matching Engine has decided that an incoming packet
   belongs to a flow which is to be measured, it searches the flow table
   to determine whether or not the flow is already present.  It does
   this by computing a hash from the packet and using it for access to
   the flow table's search index.

   When designing a hash table, one normally assumes that the objects in
   the table have a constant size.  For NeTraMet's flow table this would
   mean that each flow would contain a value for every attribute.  This,
   however, is not the case, since only those attribute values 'pushed'
   by rules during packet matching are stored for a flow.




Brownlee                     Informational                      [Page 9]

RFC 2123                Traffic Flow Measurement              March 1997


   To demonstrate this problem , let us assume that every flow in the
   table contains a value for only one attribute, SourcePeerAddress, and
   that the rule set decides whether flows belong to a specified list of
   IP networks, in which case only their network numbers are pushed.
   The rules perform this test using a variety of masks, since the
   network number allocations range from 16 to 24 bits in width.  In
   searching the flow table, the meter must distinguish between zeroes
   in the address and 'don't care' bits which had been ANDed out.  To
   achieve this it must store SourcePeerMask values in the flow table as
   well as the ANDed SourcePeerAddress values.

   In early versions of NeTraMet this problem was side-stepped by using
   multiple hash tables and relying on the user to write rules which
   used the same set of attributes and masks for all the flows in each
   table.  This was effective, but clumsy and difficult to explain.
   Later versions changed to using a single hash table, and storing the
   mask values for all the address attributes in each flow.

   The current version of the meter stores the address masks in
   compressed form.  After examining a large number of rule sets I
   realised that although a rule set may have many rules, it usually has
   a very small number of address masks.  It is a simple matter to build
   a table of address masks, and store an index to this 'mask table'
   instead of a complete mask.  NeTraMet's maximum number of masks is
   defined at compile time, up to a maximum of 256.  This allows me to
   use a single byte for each mask in the flow data structure,
   significantly reducing the structure's size.  As well as this size
   reduction, two masks can be compared by comparing their indices in
   the mask table, i.e. it reduces to a single-byte comparison.
   Overall, using a mask table seems to provide useful improvements in
   storage efficiency and execution speed.

2.3.5 Ignoring unwanted flow data

   As described in the Architecture document [1], every incoming packet
   is tested against the current rule set by the Packet Matching Engine.
   This section explains my efforts to improve NeTraMet performance on
   the PC by reducing the amount of processing required by each incoming
   packet.

   On the PC each incoming packet causes an interrupt, which NeTraMet
   must process so as to collect information about the packet.  In early
   versions I used a ring buffer with 512 slots for packet headers, and
   simply copied each packet's first 64 bytes into the next free slot.
   The packet headers were later taken from the buffer, attribute values
   were extracted from them, and the resulting 'incoming attribute
   values' records were passed to the Packet Matching Engine.




Brownlee                     Informational                     [Page 10]

RFC 2123                Traffic Flow Measurement              March 1997


   I modified the interrupt handling code to extract the attribute
   values and store them in a 'buffer slot.'  This reduced the amount of
   storage required in each slot, allowing more space for storing flows.
   It did increase slightly the amount of processing done for each
   packet interrupt, but this has not caused any problems.

   In later versions I realised that if one is only interested in
   measuring IP packets, there is no point in storing (and later
   processing) Novell or EtherTalk packets!  It is a simple matter for
   the meter to inspect a rule set and determine which Peer types are of
   interest.  If there are PushRule rules which test SourcePeerType (or
   DestPeerType), they specify which types are of interest.  If there
   are no such rules, every packet type is of interest.  The PC NeTraMet
   has a set of Boolean variables, one for each protocol it can handle.
   The values of these 'protocol' variables are determined when the
   meter begins running a new rule set.  For each incoming packet, the
   interrupt handler determines the Peer type.  If the protocol is not
   of interest, no further processing is done - the packet is simply
   ignored.  In a similar manner, if Adjacent addresses are never tested
   there is no point in copying them into the packet buffer slot.

   The overall effect of these optimisations is most noticeable for rule