Patent Publication Number: US-11652739-B2

Title: Service related routing method and apparatus

Description:
This application is a continuation of U.S. application Ser. No. 15/897,728, filed Feb. 15, 2018, the entire content of which is herein incorporated by reference. 
    
    
     TECHNICAL FIELD 
     The invention generally relates to computer networks and, more particularly, the invention relates to establishing paths interconnecting network devices across a computer network. 
     BACKGROUND 
     The Internet Protocol (“IP”) serves as the de-facto standard for forwarding data messages (“datagrams”) between network devices connected with the Internet. To that end, IP delivers datagrams across a series of network devices, such as routers and switches, in the form of one or more data packets. Current Internet devices typically forward packets one-by-one to adjacent network devices (“next hop” network devices) based essentially on the address of the destination device in the packet header. Among other benefits, this routing scheme enables network devices to forward different packets of a single datagram along different routes to reduce network congestion, or avoid malfunctioning network devices. 
     SUMMARY 
     In accordance with one embodiment of the invention, a method routes packets from a source to a destination across an IP network having a plurality of nodes (including the source and destination), and a plurality of network segments interconnecting the plurality of nodes. The source and destination are configured to use a given service. To those ends, the method receives information relating to the given service, and forms a path between the source and the destination. The path includes a) at least one intermediate node between the source and the destination and b) a plurality of specific network segments extending from the source to the destination. The plurality of specific network segments are a sub-set of the plurality of network segments. To form the path, the method assigns the plurality of specific network segments to the network path between the source and the destination as a function of the information relating to the given service. 
     A first node and a second node of the plurality of nodes may have a plurality of different network segments interconnecting the first node and the second node via two different routes. As such, there may be a plurality of different ways to communicate between two specific nodes. The method preferably assigns the specific network segments by selecting one of the plurality of network segments as a function of the information relating to the given service. Among other things, this plurality of different network segments thus may be the same type of network segments, but different paths. For example, two different network segments configured to transmit video data may interconnect two adjacent network nodes. Only one of those network segments may be assigned to the path. 
     The given service may include any of a variety of different services, such as one or more of a web service, an instant message service, a video service, and an audio delivery service. Moreover, the plurality of network segments may include a network, a physical link, or some other modality. 
     The method preferably forms the path by applying values to a set of the plurality of network segments between the source and destination. These values may be assigned as a function of a plurality of information relating to different services. When assigning, the method then may assign the plurality of specific network segments to the network path between the source and the destination as a function of the values of the set of the plurality of network segments between the source and the destination. The method then may execute a function using the values of the set of the plurality of network segments to produce a net path value. 
     Illustrative embodiments also are used with stateful routing sessions. To that end, such embodiments may establish a stateful session between the source and destination using the path. In that case, traffic between the source and destination for this service and session may traverse along the path in both directions. 
     In accordance with another embodiment, an apparatus routes packets from a source to a destination across an IP network. Like the above noted IP network, this IP network has a plurality of nodes and a plurality of network segments interconnecting the plurality of nodes. The plurality of nodes includes the source and the destination, and the source and destination are configured to use a given service. The apparatus includes an input for receiving information relating to the given service, and a router operatively coupled with the input. The router is configured to form a path between the source and the destination. This path includes a) at least one intermediate node between the source and the destination and b) a plurality of specific network segments extending from the source to the destination. The plurality of specific network segments are a sub-set of the plurality of network segments. The router is configured to assign the plurality of specific network segments to the network path between the source and the destination as a function of the information relating to the given service. 
     Illustrative embodiments of the invention are implemented as a computer program product having a computer usable medium with computer readable program code thereon. The computer readable code may be read and utilized by a computer system in accordance with conventional processes. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Those skilled in the art should more fully appreciate advantages of various embodiments of the invention from the following “Description of Illustrative Embodiments,” discussed with reference to the drawings summarized immediately below. 
         FIG.  1    schematically shows a hypothetical prior art network that may implement illustrative embodiments of the invention. 
         FIG.  2    schematically illustrates a prior art technique for fragmenting a message. 
         FIG.  3    schematically shows a hypothetical internet that may implement illustrative embodiments of the invention. 
         FIG.  4    schematically shows an exemplary IP network that may implement illustrative embodiments of the invention. 
         FIG.  5    schematically shows a router configured in accordance with illustrative embodiments of the invention. 
         FIG.  6    shows a process of forming a route across an IP network in accordance with illustrative embodiments of the invention. 
         FIG.  7    shows an example of a labeling system that may implement illustrative embodiments of the invention. 
         FIG.  8    schematically shows a hypothetical internet that includes a conventional routers and augmented IP routers (AIPRs), according to an embodiment of the present invention. 
         FIG.  9    schematically shows a layout of an Ethernet header, identifying fields used for identifying a beginning of a session, according to an embodiment of the present invention. 
         FIG.  10    schematically shows a layout of an IP header, identifying fields used for identifying a beginning of a session, according to an embodiment of the present invention. 
         FIG.  11    schematically shows a layout of a TCP header, identifying fields used for identifying a beginning of a session, according to an embodiment of the present invention. 
         FIG.  12    schematically shows a block diagram of an AIPR of  FIG.  8   , according to an embodiment of the present invention. 
         FIG.  13    shows a schematic illustration of information stored in an information base by the AIPR of  FIGS.  8  and  12   , according to an embodiment of the present invention. 
         FIG.  14    schematically shows a modified lead packet produced by the AIPR of  FIG.  9   , according to an embodiment of the present invention. 
         FIGS.  15  and  16    show flowcharts illustrating operations performed by the AIPR of  FIGS.  8  and  12   , according to an embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION 
     In illustrative embodiments, a source device (or other network device or node cooperating with the source device, such as a router) more effectively forms a path across an IP network from the source device to an ultimate destination device. To that end, each of a plurality of network segments between the source and destination devices are assigned one or more service-specific values or characteristics (“values”). Those values are assigned as a function of certain services implemented by packets transported between the source and destination devices. 
     For example, a specific network segment may be assigned a first value for web traffic, and another same or different value for video streaming traffic. The source, cooperating network device, and/or other logic then forms a path from the source device to the destination device as a function of the values assigned to the noted plurality of network segments. Specifically, if the packets are for web traffic, then the web traffic value(s) preferably are used to form the path. In a corresponding manner, if the packets are for video streaming traffic, then the video streaming traffic value(s) preferably are used to form the path. Details of various embodiments are discussed below. 
     Networks 
     Illustrative embodiments preferably are implemented on a conventional computer network. Among other things, a network includes at least two nodes and at least one link between the nodes. Nodes can include computing devices (sometimes referred to as hosts) and routers. Computers include personal computers, smart phones, automatic teller machines (ATMs) and many other types of equipment that include processors and network interfaces. Links include wired and wireless connections between pairs of nodes. In addition, nodes and/or links may be implemented completely in software, such as in a virtual machine, a software defined network, and using network function virtualization. Many networks include switches, which are largely transparent for purposes of this discussion. However, some switches also perform routing functions. For the present discussion, such routing switches are considered routers. Routers are described below. 
     A node can be directly connected to one or more other nodes, each via a distinct link. For example,  FIG.  1    schematically shows a Node A directly connected to Node B via Link 1. In a given network (e.g., within a local area network), each node has a unique network address to facilitate sending and receiving data. A network includes all the nodes addressable within the network according to the network&#39;s addressing scheme and all the links that interconnect the nodes for communication according to the network&#39;s addressing scheme. For example, in  FIG.  1   , Node A, Node B, Node C, . . . Node F and all the links 1-8 together make up a network  100 . For simplicity, a network is depicted as a cloud or as being enclosed within a cloud. 
     Nodes initiate communications with other nodes via the network, and nodes receive communications initiated by other nodes via the network. For example, a node may transmit/forward/send data (a message) to a directly connected (adjacent) node by sending the message via the link that interconnects the adjacent nodes. The message includes the network address of the sending node (the “source address”) and the network address of the intended receiving node (the “destination address”). A sending node can send a message to a non-adjacent node via one or more other nodes. For example, Node D may send a message to Node F via Node B. Using well known networking protocols, the node(s) between the source and the destination forward the message until the message reaches its destination. Accordingly, to operate properly, network protocols enable nodes to learn or discover network addresses of non-adjacent nodes in their network. 
     Nodes communicate via networks according to protocols, such as the well-known Internet Protocol (IP) and above noted Transmission Control Protocol (TCP). The protocols are typically implemented by layered software and/or hardware components according to the well-known seven-layer Open System Interconnect (OSI) model. As an example, IP operates at OSI Layer 3 (Network Layer), while the TCP operates largely at OSI Layer 4 (Transport Layer). Each layer performs a logical function and abstracts the layer below it, therefore hiding details of the lower layer. 
     For example, Layer 3 may fragment a large message into smaller packets if Layer 2 (Data Link Layer) cannot handle the message as one transmission.  FIG.  2    schematically illustrates a large message  200  divided into several pieces  202 ,  204 ,  206 ,  208 ,  210  and  212 . Each piece  202 - 212  may then be sent in a separate packet, exemplified by packet  214 . Each packet includes a payload (body) portion, exemplified by payload  216 , and a header portion, exemplified at  218 . The header portion  218  contains information, such as the packet&#39;s source address, destination address and packet sequence number, necessary or desirable for: 1) routing the packet to its destination, 2) reassembling the packets of a message, and 3) other functions provided according to the protocol. In some cases, a trailer portion is also appended to the payload, such as to carry a checksum of the payload or of the entire packet. All packets of a message need not be sent along the same path, i.e., through the same nodes, on their way to their common destination. It should be noted that although IP packets are officially called IP datagrams, they are commonly referred to simply as packets. 
     Some other protocols also fragment data into packets. For example, the well-known TCP protocol fragments data into segments, officially referred to as TCP protocol data units (PDUs). Nevertheless, in common usage, the term packet is used to refer to PDUs and datagrams, as well as Ethernet frames. 
     Most protocols encapsulate packets of higher layer protocols. For example, IP encapsulates a TCP packet by adding an IP header to the TCP packet to produce an IP packet. Thus, packets sent at a lower layer can be thought of as being made up of packets within packets. Conventionally, a component operating according to a protocol examines or modifies only information within a header and/or trailer that was created by another component, typically within another node, operating according to the same protocol. That is, conventionally, components operating according to a protocol do not examine or modify portions of packets created by other protocols. 
     In another example of abstraction provided by layered protocols, some layers translate addresses. Some layers include layer-specific addressing schemes. For example, each end of a link is connected to a node via a real (e.g., electronic) or virtual interface, such as an Ethernet interface. At Layer 2 (Data Link Layer), each interface has an address, such as a media access control (MAC) address. On the other hand, at Layer 3 using IP, each interface, or at least each node, has an IP address. Layer 3 is used to find gateways to get an IP packet from the source to the destination. 
     A router typically acts as a node that interconnects two or more distinct networks or two or more sub-networks (subnets) of a single network, thereby creating a “network of networks” (i.e., an internet). Thus, a router has at least two interfaces; i.e., one where each interface connects the router to a different network, as exemplified in  FIG.  3   . When a router receives a packet via one interface from one network, it uses information stored in its routing table to direct the packet to another network via another interface. The routing table thus contains network/next hop associations. These associations tell the router that a particular destination can optimally be reached by sending the packet to a specific router that represents a next hop on the way to the final destination. For example, if Router 1  300  receives a packet, via its Interface 1  304 , from Network 1  302 , and the packet is destined to a node in Network 3  306 , the Router 1  300  consults its router table and then forwards the packet via its Interface 2  308  to Network 2  310 . Network 2  310  will then forward the packet to Network 3  306 . The next hop association can also be indicated in the routing table as an outgoing (exit) interface to the final destination. 
     Large organizations, such as large corporations, commercial data centers and telecommunications providers, often employ sets of routers in hierarchies to carry internal traffic. For example, one or more gateway routers may interconnect each organization&#39;s network to one or more Internet service providers (ISPs). ISPs also employ routers in hierarchies to carry traffic between their customers&#39; gateways, to interconnect with other ISPs, and to interconnect with core routers in the Internet backbone. 
     A router is considered a Layer 3 device because its primary forwarding decision is based on the information in the Layer 3 IP packet—specifically the destination IP address. A conventional router does not look into the actual data contents (i.e., the encapsulated payload) that the packet carries. Instead, the router only looks at the Layer 3 addresses to make a forwarding decision, plus optionally other information in the header for hints, such as quality of service (QoS) requirements. Once a packet is forwarded, a conventional router does not retain any historical information about the packet, although the forwarding action may be collected to generate statistical data if the router is so configured. Illustrative embodiments discussed below relate to an improved apparatus and method for optimizing statistical data generation and collection. 
     As noted, when a router receives a packet via one interface from one network, the router uses its routing table to direct the packet to another network. Table 1 lists information typically found in a basic IP routing table. 
     
       
         
           
               
               
             
               
                 TABLE 1 
               
               
                   
               
             
            
               
                 Destination 
                 Partial IP address (Expressed as a bit-mask) or Complete IP 
               
               
                   
                 address of a packet&#39;s final destination 
               
               
                 Next hop 
                 IP address to which the packet should be forwarded on its 
               
               
                   
                 way to the final destination 
               
               
                 Interface 
                 Outgoing network interface to use to forward the packet 
               
               
                 Cost/Metric 
                 Cost of this path, relative to costs of other possible paths 
               
               
                 Routes 
                 Information about subnets, including how to reach subnets 
               
               
                   
                 that are not directly attached to the router, via one or more 
               
               
                   
                 hops; default routes to use for certain types of traffic or 
               
               
                   
                 when information is lacking 
               
               
                   
               
            
           
         
       
     
     Routing tables may be filled in manually, such as by a system administrator, or dynamically by the router. The router uses routing protocols to exchange information with other routers and, thereby, dynamically learns about surrounding network or internet topology. For example, routers announce their presence in the network(s), more specifically, the range of IP addresses to which the routers can forward packets. Neighboring routers update their routing tables with this information and broadcast their ability to forward packets to the network(s) of the first router. This information eventually spreads to more distant routers in a network. Dynamic routing allows a router to respond to changes in a network or internet, such as increased network congestion, new routers joining an internet and router or link failures. 
     A routing table therefore provides a set of rules for routing packets to their respective destinations. When a packet arrives, a router examines the packet&#39;s contents, such as its destination address, and finds the best matching rule in the routing table. The rule essentially tells the router which interface to use to forward the packet and the IP address of a node to which the packet is forwarded on its way to its final destination IP address. 
     With hop-by-hop routing, each routing table lists, for all reachable destinations, the address of the next node along a path to that destination, i.e., the next hop. Assuming that the routing tables are consistent, a simple algorithm of each router relaying packets to their destinations&#39; respective next hop suffices to deliver packets anywhere in a network. Hop-by-hop is a fundamental characteristic of the IP Internetwork Layer and the OSI Network Layer. 
     Thus, each router&#39;s routing table typically merely contains information sufficient to forward a packet to another router that is “closer” to the packet&#39;s destination, without a guarantee of the packet ever being delivered to its destination. In a sense, a packet finds its way to its destination by visiting a series of routers and, at each router, using then-current rules to decide which router to visit next, with the hope that at least most packets ultimately reach their destinations. 
     Note that the rules may change between two successive hops of a packet or between two successive packets of a message, such as if a router becomes congested or a link fails. Two packets of a message may, therefore, follow different paths and even arrive out of order. In other words, when a packet is sent by a source node, there is no predetermined path the packet will take between the source node and the packet&#39;s destination. Instead, the path typically is dynamically determined as the packet traverses the various routers. This may be referred to as “natural routing,” i.e., a path is determined dynamically as the packet traverses the internet. 
     It should be noted that conventionally, packets sent by the destination node back to the source node may follow different paths than the packets from the source node to the destination node. 
     In many situations, a client computer node establishes a session with a server computer node, and the client and server exchange packets within the session. For example, a client computer executing a browser may establish a session with a web server. The client may send one or more packets to request a web page, and the web server may respond with one or more packets containing contents of the web page. In some types of sessions, this back-and-forth exchange of packets may continue for several cycles. In some types of sessions, packets may be sent asynchronously between the two nodes. 
     A session has its conventional meaning; namely, it is a plurality of packets sent by one node to another node, where all the packets are related, according to a protocol. A session may be thought of as including a lead (or initial) packet that begins the session, and one or more subsequent packets of the session. A session has a definite beginning and a definite end. For example, a TCP session is initiated by a SYN packet. In some cases, the end may be defined by a prescribed packet or series of packets. For example, a TCP session may be ended with a FIN exchange or an RST. In other cases, the end may be defined by lack of communication between the nodes for at least a predetermined amount of time (a timeout time). For example, a TCP session may be ended after a defined timeout period. Some sessions include only packets sent from one node to the other node. Other sessions include response packets, as in the web client/server interaction example. A session may include any number of cycles of back-and-forth communication, or asynchronous communication, according to the protocol, but all packets of a session are exchanged between the same client/server pair of nodes. A session is also referred to herein as a series of packets. 
     A computer having a single IP address may provide several services, such as web services, e-mail services and file transfer (FTP) services. The number of addresses a computer has is orthogonal to the number of services it may provide, although it has at least one. Each service is typically assigned a port number in the range 0-65,535 that is unique on the computer. A service is, therefore, defined by a combination of the node&#39;s IP address and the service&#39;s port number. Note that this combination is unique within the network the computer is connected to, and it is often unique within an internet. Similarly, a single node may execute many clients. Therefore, a client that makes a request to a service is assigned a unique port number on the client&#39;s node, so return packets from the service can be uniquely addressed to the client that made the request. 
     The term socket means an IP address-port number combination. Thus, each service has a network-unique, and often internet-unique, service socket, and a client making a request of a service is assigned a network-unique, and sometimes internet-unique, client socket. In places, the terms source client and destination service are used when referring to a client that sends packets to make requests of a service and the service being requested, respectively. 
     Path Assignment 
     As noted above, illustrative embodiments of the invention more effectively assign paths between a source device and a destination device across an IP network. To illustrate this concept,  FIG.  4    schematically shows a simplified network that may implement various embodiments of the invention. As shown, the network includes a client coupled with two servers (“Server 1” and “Server 2”) across a network having a plurality of nodes (Nodes 1-4). The client and one or more of the servers may engage in a one directional session and/or a bi-directional session. For example, the client may initiate a session with Server 1 in which they bi-directionally communicate video data to each other (e.g., using a video chat application). To simplify this discussion, even if the communication is bi-directional, the client (i.e., the initiating device) may be considered the “source device,”, while Server 1 may be considered the “destination device.” Regardless of their labels for discussion purposes, the client and servers may more generically be considered as “network devices.” 
     In this network, each server provides at least one service. For example, Server 1 may provide a first service (“Service 1”), while Server 2 may provide a second, different service (“Service 2”). Among other things, these two servers may be separate, physically spaced apart devices (e.g., physical computers in different countries), or logical servers on a single device or system (e.g., hosted by the same physical computer as two different servers, or hosted on the same distributed computer/server system). To illustrate various embodiments, Service 1 may include video streaming traffic, while Service 2 may include web traffic/serving. Of course, those skilled in the art recognize that there are a wide variety of additional or different services that these two servers can provide. For example, these two servers can also provide audio conference services, email services, instant messaging services, etc. Moreover, each server may provide multiple services. Accordingly, discussion of the specific servers in this network is for illustrative purposes only. 
     Each node between the client and the server may be implemented as any of a variety of different network devices. For example, each node may be implemented as an IP router (discussed above). As a second example, each node may be implemented as an augmented IP router (“AIPR”), discussed below. 
     To permit communication between the nodes, the network also has a plurality of network segments (e.g., links) extending between the nodes, servers, and client.  FIG.  4    schematically shows each of those network segments generically as double-sided arrows A-G. Indeed, as known by those skilled in the art, typical IP networks have many more network segments and that shown in this simplified drawing. Moreover, as with many conventional networks, multiple network segments may connect between two adjacent nodes.  FIG.  4   , for example, shows Network Segment A and Network Segment G as both coupling between Node 1 and Node 2. 
     Each of the network segments A-G may include physical links and/or logical links. For example, Network Segment D may include the Internet and thus, effectively be a logical network segment. As another example, Network Segment A may be a physical, high-speed wired or wireless connection. As with conventional networks, the network segments of  FIG.  4    may have different associated costs and performance metrics, making each one more attractive or more appropriate to transport certain types of network traffic. Those skilled in the art should understand that various other network topologies may effectively implement illustrative embodiments. Accordingly, discussion of the specific topology of  FIG.  4    is for illustrative purposes only. 
       FIG.  5    schematically shows a router  548  that forms a path of network segments from a source device, through specific network segments and nodes, to a destination device in accordance with illustrative embodiments of the invention. Specifically, the router  548  accesses information about each of the network segments to select a set of network segments between the client and one of the two servers. For a given session, this set of network segments preferably serves as the path between the client and the server. In preferred embodiments, this path may be considered a “stateful path” (discussed below). 
     As shown, the router  548  has a plurality of components operatively connected to each other by a conventional interconnect mechanism.  FIG.  5    simply shows a bus  549  communicating each of the components. Those skilled in the art should understand that this generalized representation can be modified to include other conventional direct or indirect connections. Accordingly, discussion of the bus  549  is not intended to limit various embodiments. 
     Indeed, it should be noted that  FIG.  5    only schematically shows each of the components (i.e., an interface  558 , a segment manager  556 , a calculator  554 , and a database  552 ) as a single device that may be within a single housing. Those skilled in the art should understand that each of these components can be implemented in a variety of conventional manners, such as by using hardware, software, or a combination of hardware and software, across one or more other functional components. For example, the calculator  554  may be implemented using a plurality of microprocessors executing firmware. As another example, the calculator  554  may be implemented using one or more application specific integrated circuits (i.e., “ASICs”) and related software, or a combination of ASICs, discrete electronic components (e.g., transistors), and microprocessors. Accordingly, the representation of the calculator  554  and other components in a single box of  FIG.  5    is for simplicity purposes only. In fact, in some embodiments, the calculator  554  and other components of  FIG.  5    are distributed across a plurality of different machines—not necessarily within the same housing or chassis, and/or logically distinct. 
     It should be reiterated that the representation of  FIG.  5    is a significantly simplified representation of the router  548 . Those skilled in the art should understand that such a device may have other physical and functional components, such as central processing units, long term memory, and short-term memory. Accordingly, this discussion is not necessarily intended to suggest that  FIG.  5    represents all of the elements of the router  548 . 
     The router  548  may be a part of a larger network device that routes packets across an IP network. As shown, the router  548  has a database  552  containing data relating to the network topology and related information, such as data relating to network segments, services, nodes in the network, etc. The router  548  also has the above noted calculator  554  that applies one or more functions to values assigned to network segments, and a segment manager  556  that assigns segments to a network path between a client device and destination device. The above noted interface  558  also coupled to the bus  549  enables communication external to the router  548 . 
     The router  548  may be local to the client/source device, such as part of its local area network or even part of the client device. In other embodiments, however, the router  548  may be implemented remotely or in a distributed manner in the network. For example, the router  548  may be implemented as a web service (e.g., a SAAS or hosted service). 
       FIG.  6    shows a process of forming a route across an IP network in accordance with illustrative embodiments of the invention. It should be noted that this process is simplified from a longer process that normally may be used to form a route across an IP network. Accordingly, the process may have many steps, such as policy analysis and conflict resolution steps, which those skilled in the art likely would use. In addition, some of the steps may be performed in a different order than that shown, or at the same time. Those skilled in the art therefore can modify the process as appropriate. 
     Prior to beginning the process, the client begins initiating a session with the destination. That session relates to a service, such as a Web service (e.g., requesting access to a worldwide webpage), an audio conference service, a video conference service, a text messaging service, e-mail service, etc. Indeed, those skilled in the art recognize that a number of other services may be used and thus, the listed services are for illustrative purposes only. 
     The process begins at step  600 , in which logic receives information relating to the service (or services) that will be the subject of the session between the client and the destination (e.g., Server 1 of  FIG.  4   ). For example, the segment manager  556  on the router  548  may receive that information through the interface  558  and determine that it should produce a path from the client to the destination. As another example, the segment manager  556  may parse one or more packets it intercepts and/or receives to determine the type of service that will be the subject of the session. 
     Next, the segment manager  556  accesses the database  552  to determine the various network segments between the client and the destination. Using the network of  FIG.  4   , for example, the database  552  may list nodes 1-4 and network segments A-G. Among other places, this data may derive from the general routing table in the router  548 . In addition, the database  552  also may associate each network segment with a value for each service across such network segments. By way of example, for the network of  FIG.  4   , the database  552  may have a network segment table similar to that in Table 1 below: 
     
       
         
           
               
               
               
               
               
             
               
                   
                 TABLE 1 
               
               
                   
                   
               
               
                   
                 Network Segment 
                 Service 1 
                 Service 2 
                 Service 3 
               
               
                   
                   
               
             
            
               
                   
               
            
           
           
               
               
               
               
               
            
               
                   
                 A 
                 10 
                 2000 
                 40 
               
               
                   
                 B 
                 Never 
                 40 
                 100 
               
               
                   
                 C 
                 300 
                 60 
                 200 
               
               
                   
                 D 
                 50 
                 0 
                 10000 
               
               
                   
                 E 
                 0 
                 60 
                 40 
               
               
                   
                 F 
                 0 
                 20 
                 Never 
               
               
                   
                 G 
                 40 
                 0 
                 0 
               
               
                   
                   
               
            
           
         
       
     
     Each of the values assigned to the different services may be a policy decision based upon any of a number of variables, such as the bandwidth through that particular network segment, the quality of the network segment, the general cost of the network segment, etc. In fact, those skilled in the art may use an arbitrary policy consideration for setting those values. In this example, higher values represent a higher cost to use that network segment. Other embodiments, however, may link the values to other factors, or may use higher values to represent lower network segment costs. 
     As network conditions change, the network administrator or other person/logic may update these values periodically or a periodically. In addition, the network administrator or other person/logic may add information and/or values about other network segments, or remove information about these network segments. In some embodiments, each network segment may have two or more values for use with functions that may require more than one value. 
       FIG.  7    schematically shows an example of records in the database  552  in another format. In this example, the “service-policy” block lists the name of the service “HDvideo” and values for potential network segments for this service relative to the different network segments. In this case, HDvideo service flows/packets have a value of “10” over an network segment labeled “mpls,” and a value of “never” over a network segment labeled LTE. In this case, administrators or others within this network made the decision that LTE network segment should not be used to send high-density video. In contrast, administrators or others within this network made the decision that MPLS network segments should be encouraged to transmit high-density video because its value is relatively low (10). Accordingly, high-density video using these network segments will be transferred to the network segment across a network interface having the identity “mpls.” 
     Returning to  FIG.  6   , the process continues to step  604 , in which the calculator  554  calculates an optimal path from the client to the destination as a function of the network segment values. Specifically, the calculator  554  retrieves the values of some or all of the network segments for which it has values between the client and the destination devices. Then, the calculator  554  applies one or more functions, formulas, rules or some other process to the values assigned for the service to be used in the session for which the path is being formed. Accordingly, the calculator  554  may ignore values assigned to other services for a given network segment. 
     To illustrate this process, using Table 1, the calculator  554  may calculate values for various possible routes or paths from the client to the destination device of the network in  FIG.  4   . In this example, assume that the client requires access to the server that provides “Service 1.” Indeed, there are a number of potential options for forming a path of some subset of the plurality of network segments between the client and the destination server. Those paths may include:
         Path 1: A, B, F   Path 2: G, B, F   Path 3: D, C, F       

     As noted, the calculator  554  may select any of a wide variety of functions to calculate a total value for the various paths. The administrator may select any of a wide variety of functions for that purpose. Those functions could include first, second, or third order equations, multipliers, additive, and divisional equations. A simple function, however, simply may add the values of each network segment together to produce a total path value. In fact, preferred embodiments use such a simple function, and select the route having the lowest value—i.e., the route having the lowest effective cost in some embodiments. 
     Using the examples above with this simple additive function, the various paths have the following values:
         Path 1: A(Service 1)+B(Service 1)+F(Service 1)=10+Never+0=NEVER   Path 2: G(Service 1)+B(Service 1)+F(Service 1)=40+NEVER+0=NEVER   Path 3: D(Service 1)+C(Service 1)+F(Service 1)=50+300+0=350       

     In this example, packets transporting information relating to Service 1 
     cannot use Path 1 or Path 2 because at least one network segment on those paths has a value of “Never;” i.e., packets carrying the service cannot use specific network segments with the “Never” value. Accordingly, this example, the best and only path that may be taken of these three paths is Path 3. 
     As another example, the various paths above may have the following values if using Service 2:
         Path 1: A(Service 2)+B(Service 2)+F(Service 2)=2000+40+20=2060   Path 2: G(Service 2)+B(Service 2)+F(Service 2)=0+40+20=60   Path 3: D(Service 2)+C(Service 2)+F(Service 2)=0+60+20=80       

     Accordingly, the segment manager  556  preferably chooses the path having 
     the lowest value. In this case, that lowest value is 60 and thus, the segment manager  556  preferably selects Path 2. In this example, the service may be provision of high definition video, and Network Segment A may be an LTE segment, and Network Segment B may be an MPLS segment. The administrator or other person managing the policy may have set the values so that high definition video does not use an LTE segment, which, may be much more expensive to use than an MPLS segment. 
     In other embodiments, Network Segments A and B can be the same type of segments. For example, both could be LTE network segments, or both could be MPLS segments. In that case, both segments may have the same value, or different value depending upon other policy considerations, such as the reliability of each of those specific segments. As shown, the values can include numerical values or non-numerical values having specific meanings. In the example above, “NEVER” is a non-numerical value that means never use that network segment. Those skilled in the art can set other non-numerical values, such as “ALWAYS” or “VIDEO” (i.e., preferring video data). 
     If one of the links of Path 2 fails, however, then illustrative embodiments of the segment manager  556  may use the next lowest cost path. In this case, that next lowest cost path would be Path 3, which has a cost of 80. Illustrative embodiments of this example therefore selects the lowest cost path that does not have a failed link. Other embodiments, however, may recalculate the path values in case the network or values changed. 
     More generically, various embodiments select the path having an aggregate value that meets the prescribed criteria of the system. The example above, for instance, uses the path with the lowest total value. Other embodiments, however, may select the path having other values, such as the path of the highest total value, the path with the highest even or odd total value, etc. The path selected therefore depends upon the specific requirements deemed necessary by the policy of the network. 
     Now that the segment manager  556  has selected an appropriate path, the 
     process continues to step  606 , in which the segment manager  556  forms the path using the selected network segments. In the two examples above, the segment manager  556  forms a path using Path 3 (in the first example), or using Path 2 (in the second example). Illustrative embodiments form this path in the conventional manner, or by using the processes discussed below with regard to  FIGS.  8 - 16   . 
     The process concludes at step  608 , which routes packets to the destination using the path formed by step  606 . Accordingly, illustrative embodiments form the complete path between a first node and a second node as a function of the service used by the nodes (i.e., the type of data carried by the packets). 
     Stateful Routing 
     As noted above, the packets of a session preferably follow the same path as the lead packet of that session, at least in the forward direction, i.e., from a source client to a destination service. The subsequent packets traverse at least a subset of the routers the lead packet traverses between the source client and the destination service. Among other benefits, this stateful routing scheme more effectively enhances the benefits of collecting routing statistics. Those skilled in the art may implement such a stateful routing scheme with various embodiments. 
     Each router in the subset is referred to herein as an intermediate node or waypoint, although the waypoints are not necessarily predetermined before the lead packet is sent by the source client. While stateful routing may enable the lead packet to be naturally routed, illustrative embodiments route using a pre-specified path as discussed above with regard to  FIG.  6   . In illustrative embodiments, the subsequent packets traverse the same waypoints, and in the same order, as the lead packet. 
     While the processes below frequently reference naturally routed packets, those processes can be adapted to route packets using the paths selected by the process of  FIG.  6   . Accordingly, those skilled in the art should recognize that discussion of naturally routed packets is one embodiment and not limiting. 
     Of course, some packets may be dropped along the way, as is typical in an IP network or internet, such as by an overloaded router or due to corruption of the packet by a link. Thus, all the packets sent by the source client need not reach the session&#39;s destination service and, consequently, all the packets sent by the source client need not traverse all the waypoints. However, subsequent packets that do reach the destination service must traverse all the waypoints. For simplicity of explanation, dropped packets are ignored in the remaining discussion, and the term “all the packets” means all the packets that reach their respective destinations. 
     As a result of this forward flow control, metrics collected at one of the waypoints represent all the packets of the session. These metrics are not diluted by packets that bypass the waypoint, because no packet of the session can bypass any waypoint. Security functions, such as inspection for malicious packets, performed at one waypoint are sure to be performed on all packets of the session. Importantly, this enables statistics to be calculated for specific sessions. 
     Some embodiments also ensure that return packets from the destination service to the source client also follow the same path, i.e., traverse the waypoints, but in reverse order. This reverse flow control enables use of paths, such as via proprietary networks, which might not otherwise be available by naturally routing the return packets. 
     A packet flow controller (also referred to herein as an augmented IP router (“AIPR”) and noted above) ensures that subsequent packets of a session follow the same path as the lead packet of the session, as discussed above. In fact, any of the routers mentioned when discussing  FIGS.  4 - 7    may be implemented as AIPRs/waypoints. An AIPR also performs conventional routing functions, and also those described above with regard to statistics collection.  FIG.  8    is a schematic diagram illustrating a hypothetical set of interconnected networks  400 ,  402 ,  404  and  406 , i.e., an internet. Each network  401 - 406  includes a number of routers and AIPRs, not all of which are necessarily shown. Network  401  includes AIPR 1  408  and router  410 . Network  401  may be, for example, a network of a telecommunications carrier. Network  402  includes a router  412  and AIPR 2  414 . Network  402  may be, for example, a network of a first ISP. Network  404  includes a router  416  and AIPR 3  418 . Network  404  may be, for example, the Internet backbone or a portion thereof. Network  406  includes a router  420 , AIPR 4  422  and another router  424 . Network  406  may be, for example, a network of a second ISP. 
     Assume a source client node  426  initiates a session with a destination service node  428 . For example, the source client  426  may request a web page, and the destination service node  428  may include a web server. The source client  426  may, for example, be part of a first local area network (LAN) (not shown) within a first corporation, and the LAN may be connected to the telecommunications carrier network  401  via a gateway router  430  operated by the corporation. Similarly, the destination service node  428  may be operated by a second corporation, and it may be part of a second LAN (not shown) coupled to the network  406  of the second ISP via a gateway router  432  operated by the second corporation. As a lead packet of the session traverses the internet, each AIPR (waypoint) the packet traverses records information that eventually enables the waypoint to be able to identify its immediately previous waypoint and its immediately next waypoint, with respect to the session. 
     The lead packet of the session is naturally routed, or routed according to the process of  FIG.  6   . Assume the lead packet reaches AIPR 1  408  before it reaches network  402 ,  404  or  406 . AIPR 1  408  automatically identifies the lead packet as being an initial packet of the session. AIPR 1  408  may use various techniques to identify the beginning of a session, as noted above and as discussed in more detail below. AIPR 1  408  becomes the first waypoint along a path the lead packet eventually follows. 
     AIPR 1  408  assigns a unique identifier to the session and stores information about the session in the AIPR&#39;s database to enable the AIPR 1  408  to identify subsequent packets of the session. In some embodiments, AIPR 1  408  reads the client socket/service socket number pair in the lead packet and stores the client socket/service socket number pair in a database to uniquely identify the session. This enables the AIPR 1  408  to identify the subsequent packets as being part of the session, because all subsequent packets of the session will contain the same client socket/service socket number pair. 
     In some embodiments, AIPR 1  408  sets a flag in its database to indicate the lead packet has not traversed any other AIPR before reaching AIPR 1  408 . This flag may be used later, for example when the AIPR 1  408  handles return packets. AIPR 1  408  may be able to identify the lead packet as not having traversed any other AIPR by lack of any modification to the packet. Packet modification is described below. 
     AIPR 1  408  modifies the lead packet to indicate the lead packet has been handled by an AIPR. In some embodiments, the AIPR 1  408  stores the unique identifier of the session and, if not included in the unique identifier, the AIPR&#39;s network address in the packet to produce a modified lead packet. Subsequent AIPRs, if any, that handle the (now modified) lead packet use this modification to identify the lead packet as a lead packet that has been handled by an AIPR, and to indicate that subsequent packets of the session should be routed the same way as the lead packet is routed. 
     In some embodiments, AIPR 1  408  assigns a port number on the interface over which AIPR 1  408  will forward the lead packet. The AIPR&#39;s network address and this port number, in combination, may be used as a unique identifier of the session, at least from the point of view of the next AIPR along the path. AIPR 1  408  may include the AIPR&#39;s network address-port number combination in the modified lead packet. Thus, the next AIPR along the path may assume that subsequent packets sent from this network address-port number combination are part of, or likely to be part of, the session. 
     AIPR 1  408  then forwards the lead packet naturally or using the process of  FIG.  6   . The lead packet traverses an unspecified number of nodes of network  401  until it reaches router  410 , which routes the lead packet to network  402 . Assume the router  410  forwards the lead packet to AIPR 2  414  in network  402 . 
     AIPR 2  414  detects the modification to the lead packet, identifying a need for special treatment. AIPR 2  414  becomes the second waypoint along the path the lead packet will follow. AIPR 2  414  stores in its database the network address of AIPR 1  408  and the port number assigned by AIPR 1  408 , in association with a unique identifier of the session, such as the client and server socket number pair, thus identifying the previous waypoint along the path in association with the session. In this way, each waypoint learns the network address and port number of the previous waypoint along this session&#39;s path and uses a related association device (an “associator”) to associate this information with a session identifier. This information may be used later to forward return packets, from waypoint to waypoint, back to the source client  426 . 
     In some embodiments, AIPR 2  414  assigns a port number on the interface over which the lead packet was received. The AIPR&#39;s network address and this port number, in combination, may be used as a unique identifier of the session, at least from the point of view of AIPR 1  408 . Thus, subsequent packets addressed to this network address-port number combination may be assumed to be, or at least are likely to be, part of the session. 
     In some embodiments, AIPR 2  414  sends a packet back to AIPR 1  408  to inform AIPR 1  408  of the network address-port number combination, in association with the identification of the session. In some embodiments, the network address-port number combination are sent to AIPR 1  408  later, in connection with a return packet, as described below. In either case, AIPR 1  408  learns a network address-port number combination unique to the session, and AIPR 1  408  sends subsequent packets to that address-port combination, rather than naturally forwarding the subsequent packets. In this way, each waypoint learns the network address and port number of the next waypoint along this session&#39;s path. This information is used to forward subsequent packets, from waypoint to waypoint, forward to the destination service  428 , along the same path as the lead packet. 
     AIPR 2  214  modifies the lead packet to include the network address of AIPR 2  214 , and then forwards the lead packet. As with AIPR 1  408 , in some embodiments AIPR 2  214  assigns a port number on the interface over which AIPR 2  214  forwards the packet, and the network address of AIPR 2  214  and the port number are included in the modified lead packet AIPR 2  214  sends. 
     The lead packet traverses an unspecified number of nodes of network  402 , until it reaches router  412 , which routes the lead packet to network  404 . Assume the router  416  forwards the lead packet to AIPR 3  418 . 
     AIPR 3  418  becomes the third waypoint along the path the lead packet will follow. AIPR 3  418  operates much as AIPR 2  414 . The lead packet is then forwarded to network  406 , where it traverses AIPR 4  422 , which becomes the fourth waypoint. 
     Three scenarios are possible with respect to the last AIPR  422  (AIPR 4) along the path to the destination service  428 . 
     In the first scenario, one or more AIPRs relatively close to a destination service are provisioned to handle lead packets for the destination service. The AIPRs may be so provisioned by storing information in their databases to identify the destination service, such as by the service socket number or other unique identifier of the service. These “terminus” AIPRs broadcast their ability to forward packets to the destination service. A terminus AIPR is an AIPR that can forward packets to a destination service, without the packets traversing another AIPR. A terminus AIPR recognizes a lead packet destined to a service that terminates at the AIPR by comparing the destination service socket number to the information provisioned in the AIPR&#39;s database. 
     If AIPR 4  422  has been so provisioned, AIPR 4  422  may restore the lead packet to its original form, i.e., the form the lead packet had when the source client  426  sent the lead packet, or as the packet might have been modified by the router  430 , such as a result of network address translation (NAT) performed by the router  430 . Thus, the lead packet may be restored to a form that does not include any of the modifications made by the waypoints  408 ,  414  and  418 . AIPR 4  422  then forwards the lead packet to the destination service  428 . Like AIPR 3  418 , AIPR 4  422  stores information in its database identifying AIPR 3  418  as the previous AIPR for this session. 
     In the second scenario, AIPR 4  422  is not provisioned with information about the destination service  428 . In such embodiments, AIPR 4  422  may operate much as AIPR 2  414  and AIPR 3  418  operate. AIPR 4  422  modifies and forwards the lead packet, and the lead packet is eventually delivered to the destination service  428 . The destination service  428  responds to the lead packet. For example, if the lead packet is a SYN packet to initiate a TCP session, the destination service  428  responds with an ACK or SYN/ACK packet. AIPR 4  422  recognizes the return packet as being part of the session, such as based on the source client/destination service network address/port number pairs in the return packet. Furthermore, because the return packet was sent by the destination service  428 , and not another AIPR, AIPR 4  422  recognizes that it is the last AIPR along the path for this service. 
     AIPR 4  422  stores information in its database indicating AIPR 4  422  is a terminus AIPR. If AIPR 4  422  receives subsequent packets of the session, AIPR 4  422  may restore the subsequent packets to their original forms, i.e., the forms the subsequent packets had when the source client  426  sent the subsequent packets, or as the packets might have been modified by the router  430 , such as a result of network address translation (NAT) performed by the router  430 . AIPR 4  422  forwards the subsequent packets to the destination service  428 . 
     AIPR 4  422  modifies the return packet to include a port number on the interface AIPR 4  422  received the lead packet from AIPR 3  418 , as well as the network address of AIPR 4  422 . AIPR 4  422 , then forwards the return packet to AIPR 3  418 . Although the return packet may be forwarded by other routers, AIPR 4  422  specifically addresses the return packet to AIPR 3  418 . This begins the return packet&#39;s journey back along the path the lead packet traveled, through all the waypoints traversed by the lead packet, in reverse order. Thus, the return packet is not naturally routed back to the source client  426 . 
     AIPR 3  418  receives the modified return packet and, because the return packet was addressed to the port number AIPR 3  418  previously assigned and associated with this session, AIPR 3  418  can assume the return packet is part of, or likely part of, the session. AIPR 3  418  copies the network address and port number of AIPR 4  422  from the return packet into the AIPR&#39;s database as the next waypoint for this session. If AIPR 3  418  receives subsequent packets of the session, AIPR 3  418  forwards them to the network address and port number of the next waypoint, i.e., AIPR 4  422 . 
     Thus, once an AIPR is notified of a network address and port number of a next AIPR along a session path, the AIPR forwards subsequent packets to the next AIPR, rather than naturally routing the subsequent packets. 
     AIPR 3  418  forwards the return packet to AIPR 2  414 , whose network address and port number were stored in the database of AIPR 3  418  and identified as the previous waypoint of the session. Likewise, each of the waypoints along the path back to the source client  426  forwards the return packet to its respective previous waypoint. 
     When the first waypoint, i.e., AIPR 1  408 , receives the return packet, the waypoint may restore the return packet to its original form, i.e., the form the return packet had when the destination service  428  sent the return packet, or as the packet might have been modified by the router  430 , such as a result of network address translation (NAT) performed by the router  430 . Recall that the first waypoint set a flag in its database to indicate the lead packet had not traversed any other waypoint before reaching the first waypoint. This flag is used to signal the first waypoint to restore the return packet and forward the restored return packet to the source client  426 . The first waypoint forwards the return packet to the source client  426 . Subsequent return packets are similarly handled. 
     In the third scenario, not shown in  FIG.  8   , the last AIPR to receive the lead packet has a network address equal to the network address of the destination service. For example, the destination service network address may be given to a gateway router/AIPR, and the gateway router/AIPR may either process the service request or its router table may cause the packet to be forwarded to another node to perform the service. The last AIPR may restore the lead packet and subsequent packets, as described above. 
     It should be noted that although preferred embodiments use stateful routing as noted above, other embodiments do not use stateful routing. 
     Lead Packet Identification 
     As noted, a waypoint should be able to identify a lead packet of a session. Various techniques may be used to identify lead packets. Some of these techniques are protocol-specific. For example, a TCP session is initiated according to a well-known three-part handshake involving a SYN packet, a SYN-ACK packet and an ACK packet. By statefully following packet exchanges between pairs of nodes, a waypoint can identify a beginning of a session and, in many cases, an end of the session. For example, A TCP session may be ended by including a FIN flag in a packet and having the other node send an ACK, or by simply including an RST flag in a packet. Because each waypoint stores information about each session, such as the source client/destination service network address/port number pairs, the waypoint can identify the session with which each received packet is associated. The waypoint can follow the protocol state of each session by monitoring the messages and flags, such as SYN and FIN, sent by the endpoints of the session and storing state information about each session in its database. Such stateful monitoring of packet traffic is not taught by the prior art known to the inventor. Instead, the prior art teaches away from this type of session. 
     It should be noted that a SYN packet may be re-transmitted—each SYN packet does not necessarily initiate a separate session. However, the waypoint can differentiate between SYN packets that initiate a session and re-transmitted SYN packets based on, for example, the response packets. 
     Where a protocol does not define a packet sequence to end a session, the waypoint may use a timer. After a predetermined amount of time, during which no packet is handled for a session, the waypoint may assume the session is ended. Such a timeout period may also be applied to sessions using protocols that define end sequences. 
     Table 2 describes exemplary techniques for identifying the beginning and end of a session, according to various protocols Similar techniques may be developed for other protocols, based on the definitions of the protocols. 
     
       
         
           
               
               
               
             
               
                 TABLE 2 
               
               
                   
               
               
                 Protocol 
                 Destination Port 
                 Technique for Start/End Determination 
               
               
                   
               
             
            
               
                 TCP 
                 Any 
                 Detect start on the first SYN packet from a new address/port 
               
               
                   
                   
                 unique within the TCP protocol&#39;s guard time between address/port 
               
               
                   
                   
                 reuse. Following the TCP state machine to determine an end (FIN 
               
               
                   
                   
                 exchange, RST, or guard timeout). 
               
               
                 UDP - TFTP 
                 69 
                 Trap on the first RRQ or WRQ message to define a new session, 
               
               
                   
                   
                 trap on an undersized DAT packet for an end of session. 
               
               
                 UDP-SNMP 
                 161, 162 
                 Trap on the message type, including GetRequest, SetRequest, 
               
               
                   
                   
                 GetNextRequest, GetBulkRequest, InformRequest for a start of 
               
               
                   
                   
                 session, and monitor the Response for end of session. For SNMP 
               
               
                   
                   
                 traps, port 162 is used, and the flow of data generally travels in the 
               
               
                   
                   
                 “reverse” direction. 
               
               
                 UDP-SYSLOG 
                 514  
                 A single message protocol, thus each message is a start of session, 
               
               
                   
                   
                 and end of session. 
               
               
                 UDP-RTP 
                 Any 
                 RTP has a unique header structure, which can be 
               
               
                   
                   
                 reviewed/analyzed to identify a start of a session. This is not 
               
               
                   
                   
                 always accurate, but if used in combination with a guard timer on 
               
               
                   
                   
                 the exact same five-tuple address, it should work well enough. The 
               
               
                   
                   
                 end of session is detected through a guard timer on the five-tuple 
               
               
                   
                   
                 session, or a major change in the RTP header. 
               
               
                 UDP-RTCP 
                 Any 
                 RTCP also has a unique header, which can be reviewed, analyzed, 
               
               
                   
                   
                 and harvested for analytics. Each RTCP packet is sent periodically 
               
               
                   
                   
                 and can be considered a “start of session” with the corresponding 
               
               
                   
                   
                 RTCP response ending the session. This provides a very high 
               
               
                   
                   
                 quality way of getting analytics for RTCP at a network middle 
               
               
                   
                   
                 point, without using a Session Border Controller 
               
               
                 UDP-DNS 
                 53 
                 Each DNS query is a single UDP message and response. By 
               
               
                 (Nameserver) 
                   
                 establishing a forward session (and subsequent backward session) 
               
               
                   
                   
                 the Augmented router gets the entire transaction. This allows 
               
               
                   
                   
                 analytics to be gathered and manipulations that are appropriate at 
               
               
                   
                   
                 the Augmented router. 
               
               
                 UDP-NTP 
                 123  
                 Each DNS query/response is a full session. So, each query is a 
               
               
                   
                   
                 start, and each response is an end. 
               
               
                   
               
            
           
         
       
     
       FIG.  9    is a schematic layout of an Ethernet header  500 , including a Destination MAC Address  502  and an 802.1q VLAN Tag  504 .  FIG.  10    is a schematic layout of an IP header  600 , including a Protocol field  602 , a Source IP Address  604  and a Destination IP Address  606 .  FIG.  11    is a schematic layout of a TCP header  700 , including a Source Port  702 , a Destination Port  704 , a Sequence Number  706 , a SYN flag  708  and a FIN flag  710 . These packets and the identified fields may be used to identify the beginning of a session, as summarized in Table 3. 
     
       
         
           
               
               
               
             
               
                 TABLE 3 
               
               
                   
               
               
                 Data Item 
                 Where From 
                 Description 
               
               
                   
               
             
            
               
                 Physical 
                 Ethernet Header 
                 This is the actual port that the 
               
               
                 Interface 
                   
                 message was received on, which 
               
               
                   
                   
                 can be associated or discerned by 
               
               
                   
                   
                 the Destination MAC Address 
               
               
                 Tenant 
                 Ethernet Header 
                 Logical association with a group of 
               
               
                   
                 OR Source MAD 
                 computers. 
               
               
                   
                 Address &amp; Previous 
               
               
                   
                 Advertisement 
               
               
                 Protocol 
                 IP Header 
                 This defines the protocol in use 
               
               
                   
                   
                 and, for the TCP case, it must be 
               
               
                   
                   
                 set to a value that corresponds to 
               
               
                   
                   
                 TCP 
               
               
                 Source IP 
                 IP Header 
                 Defines the source IP Address of 
               
               
                 Address 
                   
                 the initial packet of a flow. 
               
               
                 Destination IP 
                 IP Header 
                 Defines the destination IP Address 
               
               
                 Address 
                   
                 of the initial packet of a flow. 
               
               
                 Source Port 
                 TCP Header 
                 Defines the flow instance from the 
               
               
                   
                   
                 source. This may reflect a client, a 
               
               
                   
                   
                 firewall in front of the client, or a 
               
               
                   
                   
                 carrier grade NAT. 
               
               
                 Destination 
                 TCP Header 
                 This defines the desired service 
               
               
                 Port 
                   
                 requested, such as 80 for HTTP. 
               
               
                 Sequence 
                 TCP Header 
                 This is a random number assigned 
               
               
                 Number 
                   
                 by the client. It may be updated by 
               
               
                   
                   
                 a firewall or carrier grade NAT. 
               
               
                 SYN Bit On 
                 TCP Header 
                 When the SYN bit is on, and no 
               
               
                   
                   
                 others, this is an initial packet of a 
               
               
                   
                   
                 session. It may be retransmitted if 
               
               
                   
                   
                 there is no response to the first 
               
               
                   
                   
                 SYN message. 
               
               
                   
               
            
           
         
       
     
     Augmented IP Router (AIPR) 
       FIG.  12    is a schematic block diagram of an AIPR (waypoint)  800  configured in accordance with illustrative embodiments of the invention. The AIPR  800  includes at least two network interfaces  802  and  804 , through which the AIPR  800  may be coupled to two networks. The interfaces  802  and  804  may be, for example, Ethernet interfaces. The AIPR  800  may send and receive packets via the interfaces  802  and  804 . 
     A lead packet identifier  806  automatically identifies lead packets, as discussed herein. In general, the lead packet identifier  806  identifies a lead packet when the lead packet identifier  806  receives a packet related to a session that is not already represented in the AIPR&#39;s information base  810 , such as a packet that identifies a new source client/destination service network address/port number pair. As noted, each lead packet is an initial, non-dropped, packet of a series of packets (session). Each session includes a lead packet and at least one subsequent packet. The lead packet and all the subsequent packets are sent by the same source client toward the same destination service, for forward flow control. For forward and backward flow control, all the packets of the session are sent by either the source client or the destination service toward the other. 
     A session (packet series) manager  808  is coupled to the lead packet identifier  806 . For each session, the session manager assigns a unique identifier. The unique identifier may be, for example, a combination of the network address of the AIPR  800  or of the interface  802 , in combination with a first port number assigned by the session manager  808  for receiving subsequent packets of this session. The unique identifier may further include the network address of the AIPR  800  or of the other interface  804 , in combination with a second port number assigned by the session manager  808  for transmitting the lead packet and subsequent packets. This unique identifier is associated with the session. The session manager  808  stores information about the session in an information base  810 . This information may include the unique identifier, in association with the original source client/destination service network address/port number pairs. 
       FIG.  13    is a schematic layout of an exemplary waypoint information base  900 . Each row represents a session. A session identification column  902  includes sub-columns for the source client  904  and the destination service  906 . For each client  904 , its network address  908  and port number  910  are stored. For each destination service  906 , its network address  912  and port number  914  are stored. This information is extracted from the lead packet. 
     State information about the session may be stored in a state column  915 . This information may be used to statefully follow a series of packets, such as when a session is being initiated or ended. 
     A backward column includes sub-columns for storing information  916  about a portion of the backward path, specifically to the previous AIPR. The backward path information  916  includes information  918  about the previous AIPR and information  920  about the present AIPR  800 . The information  918  about the previous AIPR includes the AIPR&#39;s network address  922  and port number  924 . The session manager  808  extracts this information from the lead packet, assuming the lead packet was forwarded by an AIPR. If, however, the present AIPR  800  is the first AIPR to process the lead packet, the information  918  is left blank as a flag. The information  920  about the present AIPR  800  includes the network address  926  of the interface  802  over which the lead packet was received, as well as the first port number  928  assigned by session manager  808 . 
     The waypoint information base  900  is also configured to store information  930  about a portion of the forward path, specifically to the next AIPR. This information  930  includes information  932  about the present AIPR  800  and information  934  about the next AIPR along the path, assuming there is a next AIPR. The information  932  includes the network address  936  of the interface over which the present AIPR will send the lead packet and subsequent packets, as well as the second port number  938  assigned by the session manager  808 . The information  934  about the next AIPR along the path may not yet be available, unless the AIPR is provisioned with information about the forward path. The information  934  about the next AIPR includes its network address  940  and port number  942 . If the information  934  about the next AIPR is not yet available, the information  934  may be filled in when the AIPR  800  processes a return packet, as described below. 
     Some embodiments of the waypoint information base  900  may include the forward information  930  without the backward information  916 . Other embodiments of the waypoint information base  900  may include the backward information  916  without the forward information  930 . Statistical information may be gathered and/or calculated using either or both forward and backward information  916 . 
     Returning to  FIG.  12   , a lead packet modifier  812  is coupled to the session manager  808 . The lead packet modifier  812  modifies the lead packet to store the unique identifier associated with the session. The original source client network address/port number pair, and the original destination service network address/port number pair, are stored in the modified lead packet, if necessary. The lead packet may be enlarged to accommodate the additional information stored therein, or existing space within the lead packet, such a vendor specific attribute field, may be used. Other techniques for transmitting additional information are protocol specific, for example with TCP, the additional information could be transmitted as a TCP Option field, or added to the SYN packet as data. In either case, the term session data block is used to refer to the information added to the modified lead packet. 
       FIG.  14    is a schematic diagram of an exemplary modified lead packet  1000  showing the original source and destination IP addresses  1002  and  1004 , respectively, and the original source and destination port numbers  1006  and  1008 , respectively.  FIG.  14    also shows a session data block  1010  in the modified lead packet  1000 . Although the session data block  1010  is shown as being contiguous, it may instead have its contents distributed throughout the modified lead packet  1000 . The session data block  1010  may store an identification of the sending AIPR, i.e., an intermediate node identifier  1012 , such as the network address of the second network interface  804  and the second port number. 
     Returning to  FIG.  12   , the lead packet modifier  812  updates the packet length, if necessary, to reflect any enlargement of the packet. The lead packet modifier  812  updates the checksum of the packet to reflect the modifications made to the packet. The modified lead packet is then transmitted by a packet router  814 , via the second network interface  804 . The modified lead packet is naturally routed, unless the AIPR  800  has been provisioned with forward path information, such as by using the process of  FIG.  6   . 
     Eventually, the destination service sends a return packet. The AIPR  800  receives the return packet via the second interface  804 . If another AIPR (downstream AIPR) between the present AIPR  800  and the destination service handles the lead packet and the return packet, the downstream AIPR modifies the return packet to include the downstream AIPR&#39;s network address and a port number. A downstream controller  816  identifier uses stateful inspection, as described herein, to identify the return packet. The downstream controller  816  stores information  934  ( FIG.  13   ), specifically the network address and port number, about the next AIPR in the waypoint information base  900 . 
     The present AIPR  800  may use this information to address subsequent packets to the next AIPR. Specifically, a subsequent packet modifier  818  may set the destination address of the subsequent packets to the network address and port number  940  and  942  ( FIG.  13   ) of the next waypoint, instead of directly to the destination service. The packet router  814  sends the subsequent packets, according to their modified destination addresses. Thus, for each series of packets, subsequent packets flow through the same downstream packet flow controllers as the lead packet of the series of packets. 
     A last packet identifier  820  statefully follows each session to identify an end of each stream, as discussed above. As noted, in some cases, the end is signified by a final packet, such as a TCP packet with the RST flag set or a TCP ACK packet in return to a TCP packet with the FIN flag set. In other cases, the end may be signified by a timer expiring. When the end of a session is detected, the packet series manager  808  disassociates the unique identifier from the session and deletes information about the session from the waypoint information base  900 . 
     Where the AIPR  800  is provisioned to be a last AIPR before a destination service, the lead packet modifier  806  restores the lead packet to the state the lead packet was in when the source client sent the lead packet, or as the lead packet was modified, such as a result of network address translation (NAT). Similarly, the subsequent packet modifier  818  restores subsequent packets. 
     Similarly, if the destination address of the lead packet is the same as the network address of the AIPR  800 , or its network interface  802  over which it receives the lead packets, the lead packet modifier  806  and the subsequent packet modifier  818  restore the packet and subsequent packets. 
     As noted, in some protocols, several packets are required to initiate a session, as with the SYN-SYN/ACK-ACK handshake of the TCP. Thus, the downstream controller identifier  816  may wait until a second return packet is received from the destination service before considering a session as having started. 
     As noted, some embodiments of the waypoint  800  also manage return packet paths. The lead packet identifier  806  automatically ascertains whether a lead packet was forwarded to the waypoint  800  by an upstream waypoint. If the lead packet includes a session data block, an upstream waypoint forwarded the lead packet. The packet series manager  808  stores information about the upstream waypoint in the waypoint information base  810 . A return packet identifier  822  receives return packets from the second network interface  804  and automatically identifies return packets of the session. These return packets may be identified by destination address and port number being equal to the information  932  ( FIG.  13   ) in the waypoint information base corresponding to the session. A return packet modifier modifies the return packets to address them to the upstream waypoint for the session, as identified by the information  918  in the waypoint information base  900 . 
       FIG.  15    shows a flowchart schematically illustrating some operations performed by the AIPR  800  ( FIG.  12   ) in accordance with illustrative embodiments of the invention. The flowchart illustrates a packet routing method for directing packets of a session from an originating node toward a destination node in an IP network. At step  1502 , an intermediate node obtains a lead packet of a plurality of packets in a session. The intermediate node may include a routing device or a switching device that performs a routing function. 
     The packets in the session have a unique session identifier. At step  1504 , a prior node, through which the lead packet traversed, is determined. The prior node has a prior node identifier. At step  1506 , a return association is formed between the prior node identifier and the session identifier. At step  1508 , the return association is stored in memory to maintain state information for the session. 
     At step  1510 , the lead packet is modified to identify at least the intermediate node. At step  1512 , the lead packet is forwarded toward the destination node though an intermediate node electronic output interface to the IP network. The electronic output interface is in communication with the IP network. At step  1514 , a backward message (e.g., a packet, referred to as a “backward packet”) is received through an electronic input interface of the intermediate node. The backward message is received from a next node. The next node has a next node identifier. The backward message includes the next node identifier and the session identifier. The electronic input interface is in communication with the IP network. 
     At step  1516 , a forward association is formed between the next node identifier and the session identifier. At step  1518 , the forward association is stored in memory, to maintain state information for the session. At step  1520 , additional packets of the session are obtained. At step  1522 , substantially all of the additional packets in the session are forwarded toward the next node, using the stored forward association. The additional packets are forwarded through the electronic output interface of the intermediate node. 
     At step  1524 , a plurality of packets is received in a return session, or a return portion of the session, from the destination. The return session is addressed toward the originating node. At step  1526 , substantially all the packets in the return session are forwarded toward the prior node, using the stored return association. The packets are forwarded through the electronic output interface. 
     As shown at step  1600  in  FIG.  16   , forwarding the lead packet  1412  toward the destination node may include accessing a routing information base having routing information for the next node. As shown at step  1602 , the intermediate node may have a routing table, and forwarding the lead packet  1412  toward the destination node may include using the routing table to forward the lead packet toward the destination node. As shown at step  1604 , forwarding the lead packet  1412  toward the destination node may include using the next node identifier to address the lead packet toward the next node. 
     The lead packet may be addressed so that a plurality of network devices receive the lead packet after it is forwarded and before the next node receives the lead packet. 
     An AIPR  800  and all or a portion of its components  802 - 824  may be implemented by a processor executing instructions stored in a memory, hardware (such as combinatorial logic, Application Specific Integrated Circuits (ASICs), Field-Programmable Gate Arrays (FPGAs) or other hardware), firmware or combinations thereof. In a similar manner, the routing device utility  510  also may be implemented by a processor executing instructions stored in a memory, hardware (such as combinatorial logic, Application Specific Integrated Circuits (ASICs), Field-Programmable Gate Arrays (FPGAs) or other hardware), firmware or combinations thereof. 
     Various embodiments of the invention may be implemented at least in part in any conventional computer programming language. For example, some embodiments may be implemented in a procedural programming language (e.g., “C”), or in an object oriented programming language (e.g., “C++”). Other embodiments of the invention may be implemented as a pre-configured, stand-along hardware element and/or as preprogrammed hardware elements (e.g., application specific integrated circuits, FPGAs, and digital signal processors), or other related components. 
     In an alternative embodiment, the disclosed apparatus and methods (e.g., see the various flow charts described above) may be implemented as a computer program product for use with a computer system. Such implementation may include a series of computer instructions fixed either on a tangible, non-transitory medium, such as a computer readable medium (e.g., a diskette, CD-ROM, ROM, or fixed disk). The series of computer instructions can embody all or part of the functionality previously described herein with respect to the system. 
     Those skilled in the art should appreciate that such computer instructions can be written in a number of programming languages for use with many computer architectures or operating systems. Furthermore, such instructions may be stored in any memory device, such as semiconductor, magnetic, optical or other memory devices, and may be transmitted using any communications technology, such as optical, infrared, microwave, or other transmission technologies. 
     Among other ways, such a computer program product may be distributed as a removable medium with accompanying printed or electronic documentation (e.g., shrink wrapped software), preloaded with a computer system (e.g., on system ROM or fixed disk), or distributed from a server or electronic bulletin board over the network (e.g., the Internet or World Wide Web). In fact, some embodiments may be implemented in a software-as-a-service model (“SAAS”) or cloud computing model. Of course, some embodiments of the invention may be implemented as a combination of both software (e.g., a computer program product) and hardware. Still other embodiments of the invention are implemented as entirely hardware, or entirely software. 
     Although the above discussion discloses various exemplary embodiments of the invention, it should be apparent that those skilled in the art can make various modifications that will achieve some of the advantages of the invention without departing from the true scope of the invention.