Abstract:
Methods and systems for finding a packet&#39;s routing path in a network includes intercepting control messages sent by a controller to one or more switches in a software defined network (SDN). A state of the SDN at a requested time is emulated and one or more possible routing paths through the emulated SDN is identified by replaying the intercepted control messages to one or more emulated switches in the emulated SDN. The one or more possible routing paths correspond to a requested packet injected into the SDN at the requested time.

Description:
RELATED APPLICATION INFORMATION 
       [0001]    This application claims priority to provisional application No. 61/917,072, filed Dec. 17, 2013, and the contents thereof are incorporated herein by reference. 
     
    
     BACKGROUND OF THE INVENTION 
       [0002]    Software defined networks (SDNs) feature an emerging class of network architectures called forwarding architectures. These architectures split control plane decision-making off from data plane forwarding. In doing so, they enable custom programmability and centralization of the control plane while allowing for commodity high-throughput, high-fanout data plane forwarding elements. 
         [0003]    However, debugging operational SDNs can be a daunting task due to their size, distributed state, and high complexity in the controller software. The debugging tool set available to network operators is limited. Existing debugging solutions use online packet or flowtable dumping in SDN switches to determine the precise routing paths that data packets took in the network, each of which has its own drawbacks. 
       BRIEF SUMMARY OF THE INVENTION 
       [0004]    A method for finding a packet&#39;s routing path in a network includes intercepting control messages sent by a controller to one or more switches in a software defined network (SDN). A state of the SDN at a requested time is emulated and one or more possible routing paths through the emulated SDN is identified by replaying the intercepted control messages to one or more emulated switches in the emulated SDN. The one or more possible routing paths correspond to a requested packet injected into the SDN at the requested time. 
         [0005]    A system for finding a packet&#39;s path in a network includes a proxy configured to intercept control messages sent by a controller to one or more switches in an SDN. A network emulator comprising a processor is configured to emulate a state of the SDN at a requested time and to identify one or more possible routing paths through the emulated SDN by replaying the intercepted control messages to one or more emulated switches in the emulated SDN. The one or more routing possible paths correspond to a requested packet inserted into the SDN at the requested time. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0006]      FIG. 1  is a block/flow diagram illustrating a software defined networking (SDN) shadow system in accordance with the present principles. 
           [0007]      FIG. 2  is a block/flow diagram illustrating the reconstruction of switch control states in an SDN in accordance with the present principles. 
           [0008]      FIG. 3  is a block diagram of an SDN shadow system in accordance with the present principles. 
       
    
    
     DETAILED DESCRIPTION 
       [0009]    Embodiments of the present invention support offline queries on the precise routing paths that data packets take in a forwarding architecture network without instrumentation or tracing in software defined networking (SDN) switches. This includes recording he control messages exchanged between an SDN controller and switches, along with measurements of the network latency between the SDN controller and switches. 
         [0010]    Referring now to  FIG. 1 , an exemplary forwarding architecture network is shown. A software defined network  100  includes a source host  101  which communicates with a destination host  104  via, in this case, a first switch  102  and a second switch  103 . It should be understood that the precise path of packets from the source host  101  to the destination host  104  can change as the logical network structure is reconfigured by switches  102  and  103 . 
         [0011]    Control messages between the switches  102  and  103  and a controller  118 , which change flow tables in the switches  102  and  103 , are recorded, along with measurements of the network latency between the controller  118  and the switches  102  and  103 . To accomplish this, an SDN Shadow block  106  is interposed between the controller  118  and the SDN  100 . The primary purpose of the control messages is to add, delete, and modify flow/group entries in the flow tables and to set switch port properties. A proxy  108  intercepts control messages from SDN controller  118  and stores them in control plane logs  110 . The control messages can be obtained by using existing tools, such as packet sniffers, or by specialized plugins in the controller software, to create a local copy. The proxy  108  also records the time that each control message is sent, the network latency in round trip time between the controller  118  and the switches  102  and  103 . At the beginning of recording, the proxy  108  also logs a snapshot of the flow tables in the switches if they are not empty and logs the SDN network topology information, including switch information, network links between switches, and last-hop links between switches and interested hosts. 
         [0012]    To find path information, control message traces are played back in a network emulator upon a precise routing path query for a data packet at a certain time in the recording period in the query engine  114 , using information from network topology storage  112 . The query engine  114  offers a user interface to take a data packet and time stamp as inputs and runs a the network emulator to replay the selected set of recorded control messages to determine the path the data packet could take if it were injected into the SDN  100  at the time specified. Possible flow table states at the switches in question are reconstructed and the possible routing paths that the data packet in question could take are found at path API  116 . Optionally the possibilities assigned to those routing paths are calculated. This information is output in block  120  and may be in the form of an ordered list that encodes the switches traversed, the switch input and output ports, and a matched flow entry. 
         [0013]    Accepting the query input in the query engine  114  includes receiving a packet event, defined by the packet, the time, and an input switch. The packet may be in the format of a network packet that includes an Ethernet frame and IP header. Time T specifies the time when the packet entered the SDN network  100 . The input switch information is optional and may specify the first switch and port where the packet arrived in the network  100 . Contrary to existing path-oriented request tracing solutions, the query engine  114  allows users to input a packet event in the format &lt;packet X, time T, [switch S 0 :portIN]&gt; and receive a reply on the precise path information that the network packet could take in the network  100 . 
         [0014]    Rebuilding the switch flow tables selects a subset of the recorded control messages and creates an emulation of the original SDN network with the recorded network topology information, re-injects the selected set of control messages through an emulated controller to the emulated switches, and then dumps the related flow table entry information from all the emulated switches. 
         [0015]    The emulation information is then searched to find which switches and routing rules the packet could pass through, constructing precise routing paths. The path API  116  outputs paths with the format of an ordered list as described above to generate the output  120 . 
         [0016]    Referring now to  FIG. 2 , detail on the reconstruction of the control state  200  is shown. Block  202  selects recorded control messages given an input packet and a queried arrival time. Block  202  finds the set of recorded control messages that could possibly affect routing decisions for the packet. If the user provides the first hop switch information, the starting switch set is initialized accordingly. Otherwise, the starting switch set is initialized as including all available switches and their ports. For each first-hop switch, a mean return trip time (RTT) between the controller  118  and the switch is computed with a respective variance is determined. This is based on network latency information recorded by the proxy  108 . 
         [0017]    A starting time T s  is determined, defined as the time before which switch states will not influence routing decisions for the packet. If, for every control message that is sent to a switch matching the packet and incoming port on the packet fields, the control message has a recorded time stamp T i  that satisfies: 
         [0000]    
       
         
           
             
               
                 T 
                 i 
               
               + 
               
                 
                   E 
                   RTT 
                 
                 2 
               
               + 
               
                 k 
                  
                 
                     
                 
                  
                 
                   σ 
                   RTT 
                 
               
             
             &lt; 
             
               
                 
                   T 
                   0 
                 
                  
                 
                     
                 
                  
                 OR 
                  
                 
                     
                 
                  
                 
                   T 
                   i 
                 
               
               + 
               
                 
                   E 
                   RTT 
                 
                 2 
               
               - 
               
                 k 
                  
                 
                     
                 
                  
                 
                   σ 
                   RTT 
                 
               
             
             &gt; 
             
               T 
               0 
             
           
         
       
     
         [0000]    where T s =T 0 , where E RTT  is the mean RTT, σ RTT  is the variance on the RTT, T 0  is the input timestamp, and k is the Z-value in the statistical confidence interval. If not, then 
         [0000]    
       
         
           
             
               
                 T 
                 s 
               
               = 
               
                 
                   T 
                   x 
                 
                 + 
                 
                   
                     E 
                     RTT 
                   
                   2 
                 
                 - 
                 
                   k 
                    
                   
                       
                   
                    
                   
                     σ 
                     RTT 
                   
                 
               
             
             , 
           
         
       
     
         [0000]    where T x  is the time stamp of the earliest control message matching the packet and violating the above condition. 
         [0018]    All recorded control messages sent to the respective initial switch are selected which have time stamps no later than T s  and contain flow table entries matching the packet and incoming port on the packet fields. These control messages are put in a time-ordered list. If there are no such messages, then the switch in question is removed from consideration as an initial switch. If there are no switches having such control messages, then the user is informed that no valid path was found. 
         [0019]    Creating the emulated network in block  204  uses the recorded network topology information  112  to form an emulated network having the same topology as the traced SDN network  100 . 
         [0020]    Reconstructing the flow table in block  206  uses the packet, the input timestamp T s , and the results of blocks  202  and  204  to reconstruct switch flow table entries that affect the packet&#39;s routing decisions. Reconstruction begins with initializing all of the flow tables of all emulated switches with logged snapshots. An emulated controller sends recorded control messages to each emulated switch in time order until the first message is found that goes through without generating an error message and that has a time stamp T c0  such that 
         [0000]    
       
         
           
             
               
                 T 
                 
                   c 
                    
                   
                       
                   
                    
                   0 
                 
               
               + 
               
                 
                   E 
                   RTT 
                 
                 2 
               
               - 
               
                 k 
                  
                 
                     
                 
                  
                 
                   σ 
                   RTT 
                 
               
               ⋂ 
               
                 [ 
                 
                   
                     T 
                     s 
                   
                   , 
                   
                     
                       T 
                       s 
                     
                     + 
                     
                       T 
                       D 
                     
                   
                 
                 ] 
               
             
             ≠ 
             
               ∅ 
                
               
                   
               
                
               and 
             
           
         
       
       
         
           
             
               
                 
                   T 
                   
                     c 
                      
                     
                         
                     
                      
                     0 
                   
                 
                 + 
                 
                   
                     E 
                     RTT 
                   
                   2 
                 
                 + 
                 
                   k 
                    
                   
                       
                   
                    
                   
                     σ 
                     RTT 
                   
                 
                 ⋂ 
                 
                   [ 
                   
                     
                       T 
                       s 
                     
                     , 
                     
                       
                         T 
                         s 
                       
                       + 
                       
                         T 
                         D 
                       
                     
                   
                   ] 
                 
               
               ≠ 
               ∅ 
             
             , 
           
         
       
     
         [0000]    where T D  is the maximum time a packet can remain in the network and is a function of network diameter. This message and any remaining control messages satisfying the same conditions are copied into a time ordered list called Potential(S 0 ) that includes all of the control messages that potentially affect the routing decision on the packet at the switch S 0 . 
         [0021]    Three hash tables are initialized: RoutingTree(S 0 ), storedStates(S 0 ), and storedHops(S 0 ). The packet is applied to the current flow table of the emulated switch S 0  and the first flow table entry E having an output action and matching the packet and incoming port is found. If no entry is found, then there is no forwarding action for the packet at this point. If the list Potential(S 0 ) is not empty, the next control message is selected and applied to the current flow table. This is repeated until either Potential(S 0 ) is empty or a matching entry is found. 
         [0022]    The entry&#39;s output action specifies the next port. If RoutingTree(S 0 ) already includes an entry corresponding to the same switch and next port, then the next control message is selected and applied to the current flow table to search for new next ports. Otherwise, a new hash table entry is created and inserted into RoutingTree(S 0 ). 
         [0023]    The stored network topology information is used to find the other end of the network link connected to the next port. If there is no such link information, then the next control message is selected and applied to the current flow table. Otherwise processing continues from the connected switch (called the current switch in the following) and port. 
         [0024]    All control messages sent to the current switch, having a timestamp no later than T s  and having control flow table entries that match the packet and incoming port on the packet fields, are put into a time ordered list activeMSG. If the list is empty, the hash table for the entry is updated to indicate in the tree that a dead end has been reached. If there are entries in the list, the emulated controller sends the control messages in the list to the emulated current switch in the same time order until the first message is found that satisfies the same timestamp condition set forth above. 
         [0025]    The qualifying messages are copied into a time ordered list Potential(currentSwitch), as these messages potentially affect the routing decision on the packet. They are used to record all possible next-hop routing decisions for the packet in the current switch. The packet is applied to the current flow table of the emulated switch currentSwitch and the first flow table entry F having an output action and matching the packet and incoming port is found. If there is no such entry, and if Potential(currentSwitch) is not empty, the first control message in the list is selected and applied to the emulated switch currentSwitch. The message is removed from Potential(currentSwitch). 
         [0026]    The output action of F specifies the next port. The hash table is updated iwth an entry identifying the next port. If there is already an entry in storedHops(S 0 ) for currentSwitch on the current input point then a routing loop is detected and the message is removed from Potential(S 0 ). Otherwise, a new key is inserted into storedHops(S 0 ). 
         [0027]    If Potential(currentSwitch) is empty or uniitialized, the state is rolled back to the previous switch and the entry for the hop is deleted from storedStates(S 0 ) and storedHops(S 0 ). The entire set of potential messages is recursively evaluated in this way to build a set of one or more possible paths that the packet could have taken through the network  100 . Once RoutingTree(S 0 ) is complete, it can be searched for feasible routing paths to generate the output  120 . 
         [0028]    The routing paths may be searched by repeating, for each key in RoutingTree(S 0 ), a depth-first search. Whenever a leaf node is reached, the complete path from the root node to the leaf node is recorded with the concatenated per-node value information in the format of an ordered list. These lists may then be returned to the users to represent the recorded precise routing paths. 
         [0029]    It should be understood that embodiments described herein may be entirely hardware, entirely software or including both hardware and software elements. In a preferred embodiment, the present invention is implemented in hardware and software, which includes but is not limited to firmware, resident software, microcode, etc. 
         [0030]    Embodiments may include a computer program product accessible from a computer-usable or computer-readable medium providing program code for use by or in connection with a computer or any instruction execution system. A computer-usable or computer readable medium may include any apparatus that stores, communicates, propagates, or transports the program for use by or in connection with the instruction execution system, apparatus, or device. The medium can be magnetic, optical, electronic, electromagnetic, infrared, or semiconductor system (or apparatus or device) or a propagation medium. The medium may include a computer-readable storage medium such as a semiconductor or solid state memory, magnetic tape, a removable computer diskette, a random access memory (RAM), a read-only memory (ROM), a rigid magnetic disk and an optical disk, etc. 
         [0031]    A data processing system suitable for storing and/or executing program code may include at least one processor coupled directly or indirectly to memory elements through a system bus. The memory elements can include local memory employed during actual execution of the program code, bulk storage, and cache memories which provide temporary storage of at least some program code to reduce the number of times code is retrieved from bulk storage during execution. Input/output or I/O devices (including but not limited to keyboards, displays, pointing devices, etc.) may be coupled to the system either directly or through intervening I/O controllers. 
         [0032]    Network adapters may also be coupled to the system to enable the data processing system to become coupled to other data processing systems or remote printers or storage devices through intervening private or public networks. Modems, cable modem and Ethernet cards are just a few of the currently available types of network adapters. 
         [0033]    Referring now to  FIG. 3 , an SDN shadow system  300  is shown. A processor  302  interfaces with a memory  304  to identify and output the paths that a given packet may take through an SDN  100 . A controller proxy module  306  receives information from the SDN controller  118  and stores control messages in the memory  304  as control plane logs  308 . In addition, the proxy  306  stores network topology information  310  and any available network status information such as mean RTT time and RTT variance. 
         [0034]    A user interface  312  interfaces with query engine  314  to provide a user with the ability to enter a query for a specific packet at a given timestamp. The packet information includes packet headers. The query may furthermore optionally include information relating to the initial switch at which the packet entered the network  100 . The query engine  114  provides the user&#39;s query to a network emulator  316  which uses a processor  302  to emulate the network  100  based on the control plane logs  308  and the stored network topology, creating a set of possible paths that the packet could have taken through the network. These possible paths are then displayed to the user through the user interface  312 . 
         [0035]    The foregoing is to be understood as being in every respect illustrative and exemplary, but not restrictive, and the scope of the invention disclosed herein is not to be determined from the Detailed Description, but rather from the claims as interpreted according to the full breadth permitted by the patent laws. Additional information is provided in Appendix A to the application. It is to be understood that the embodiments shown and described herein are only illustrative of the principles of the present invention and that those skilled in the art may implement various modifications without departing from the scope and spirit of the invention. Those skilled in the art could implement various other feature combinations without departing from the scope and spirit of the invention.