METHOD AND SYSTEM FOR SECURED INFORMATION EXCHANGE BETWEEN INTERMEDIATE AND ENDPOINT NODES IN A COMMUNICATIONS NETWORK

TECHNICAL FIELD

[0001] Embodiments of the invention relate to the field of networking; and more specifically, to secured information exchange between intermediate and endpoint nodes in a communications network.

BACKGROUND ART

[0002] There has been significant discussion about signaling between intermediate and endpoint nodes along an end-to-end path in a communications network (also referred to simply as network). For example, Internet Engineering Task Force (IETF) has Birds of a Feather (BoF) sessions on Session Protocol for User Datagrams (SPUD) and Path Layer User Datagram Protocol (UDP) Substrate (PLUS). A sender of an UDP/ Internet Protocol (IP) packet does not normally know which nodes will be along the path travelled by its packets. Thus, as of now, explicit addressing of these nodes is not possible. It is also difficult to prevent information manipulation added by any of these nodes along the same path. With cleartext information (cleartext may also be referred to as plaintext, and it is unencrypted information that may be encrypted using one or more cryptographic algorithms), it is possible that any node on the path can read and, thus, also easily decide to edit or even remove content, if it sees benefit in doing so.

[0003] Yet some of the information a node could add can be privacy (or otherwise) sensitive. For example, a data object informing about the address remapping that has occurred will reveal information about the private network's addressing structure, which is something the initiating node already knows but is not normally exposed to the external network.

[0004] A significant issue is that an IP node, which forwards and possibly modifies IP or transport protocol header, commonly does not have any established security context to either source or destination of the IP packet, e.g., via an authenticated encrypted connection. The security context includes the information necessary to secure data objects to a peer.

Additionally, the IP node needs to know a peer node’s identity that the IP node is expected to communicate with. By enabling nodes (both endpoints and on-path nodes) to exchange information, one of the main challenges is to establish the security model for such

communication. SUMMARY

[0005] Embodiments of the disclosed techniques include methods for secured information exchange between intermediate and endpoint network devices in a communications network. In one embodiment, a method is performed by a network device that is on a path of a traffic flow between a source network device and a destination network device. The method includes receiving an Internet Protocol (IP) packet of a traffic flow sourced from the source network device and destined for the destination network device, the IP packet including a transport protocol payload. The method further includes inserting traffic flow information into the IP packet, where the network device encrypts the traffic flow information prior to the inserting; and the method continues with transmitting the IP packet after the inserting toward the destination network device, where the IP packet after the inserting includes the encrypted traffic flow information and encryption information to allow another network device to decrypt the encrypted traffic flow information.

[0006] Embodiments of the disclosed techniques include network devices for secured information exchange between intermediate and endpoint (source/destination) network devices in a communications network. In one embodiment, a network device comprises a processor and non-transitory computer-readable storage medium that provides instructions that, when executed by the processor, cause the network device to perform one or more methods for secured information exchange between the network device and an endpoint network device. One method includes receiving an Internet Protocol (IP) packet of a traffic flow sourced from a source network device and destined for a destination network device, the IP packet including a transport protocol payload. The method further includes inserting traffic flow information into the IP packet, where the network device encrypts the traffic flow information prior to the inserting; and the method continues with transmitting the IP packet after the inserting toward the destination network device, where the IP packet after the inserting includes the encrypted traffic flow information and encryption information to allow another network device to decrypt the encrypted traffic flow information.

[0007] Embodiments of the disclosed techniques include non-transitory computer-readable storage media for secured information exchange between intermediate and endpoint

(source/destination) network devices in a communications network. In one embodiment, a non- transitory computer-readable storage medium provides instructions that, when executed, cause a network device to perform one or more methods for secured information exchange between the network device and an endpoint network device. One method includes receiving an Internet Protocol (IP) packet of a traffic flow sourced from a source network device and destined for a destination network device, the IP packet including a transport protocol payload. The method further includes inserting traffic flow information into the IP packet, where the network device encrypts the traffic flow information prior to the inserting; and the method continues with transmitting the IP packet after the inserting toward the destination network device, where the IP packet after the inserting includes the encrypted traffic flow information and encryption information to allow another network device to decrypt the encrypted traffic flow information.

[0008] Embodiments of the disclosed techniques provide ways for a network device that performs operations on a packet of a traffic flow, to notify securely the initiating network device of the traffic flow about traffic flow information.

BRIEF DESCRIPTION OF THE DRAWINGS

[0009] The invention may best be understood by referring to the following description and accompanying drawings that are used to illustrate embodiments of the invention. In the drawings:

[0010] Figure 1 shows address translation in a communications networks according to some embodiments of the invention.

[0011] Figure 2A shows implementing UDP Options for secured communications between middlebox and endpoint nodes according to some embodiments of the invention.

[0012] Figure 2B shows an exemplary information object within a UDP options field according to some embodiments of the invention.

[0013] Figure 2C shows an exemplary structure of protected data according to some embodiments of the invention.

[0014] Figure 3A shows an exemplary structure of cleartext data generated by a middlebox according to some embodiments of the invention.

[0015] Figure 3B shows information included in another cleartext data object generated by a middlebox according to some embodiments of the invention.

[0016] Figure 4 shows implementing IPv6 Destination Header Extension for secured communications between middlebox and endpoint nodes according to some embodiments of the invention.

[0017] Figure 5 shows a protection envelope that would allow for adding various cleartext data entries according to some embodiments of the invention.

[0018] Figure 6 is a flow diagram illustrating the operations at a network device that is on a path between a source network device and destination network device according to some embodiments of the invention. [0019] Figure 7 is a flow diagram illustrating the operations at a destination network device of a path from a source network device, passing through an intermediate network device, and to the destination network device according to some embodiments of the invention.

[0020] Figure 8 is a flow diagram illustrating the operations at a source network device of a path from the source network device, passing through an intermediate network device, and for a destination network device according to some embodiments of the invention.

[0021] Figure 9A illustrates connectivity between network devices (NDs) within an exemplary network, as well as three exemplary implementations of the NDs, according to some embodiments of the invention.

[0022] Figure 9B illustrates an exemplary way to implement a special-purpose network device according to some embodiments of the invention.

[0023] Figure 9C illustrates various exemplary ways in which virtual network elements (VNEs) may be coupled according to some embodiments of the invention.

[0024] Figure 9D illustrates a network with a single network element (NE) on each of the NDs, and within this straight forward approach contrasts a traditional distributed approach (commonly used by traditional routers) with a centralized approach for maintaining reachability and forwarding information (also called network control), according to some embodiments of the invention.

[0025] Figure 9E illustrates the simple case of where each of the NDs implements a single NE, but a centralized control plane has abstracted multiple of the NEs in different NDs into (to represent) a single NE in one of the virtual network(s), according to some embodiments of the invention.

[0026] Figure 9F illustrates a case where multiple VNEs are implemented on different NDs and are coupled to each other, and where a centralized control plane has abstracted these multiple VNEs such that they appear as a single VNE within one of the virtual networks, according to some embodiments of the invention.

DETAILED DESCRIPTION

[0027] The following description describes methods and apparatus for secured information exchange between intermediate and endpoint nodes in a communication network. In the following description, numerous specific details such as logic implementations, opcodes, means to specify operands, resource partitioning/sharing/duplication implementations, types and interrelationships of system components, and logic partitioning/integration choices are set forth in order to provide a more thorough understanding of the present invention. It will be appreciated, however, by one skilled in the art that the invention may be practiced without such specific details. In other instances, control structures, gate level circuits and full software instruction sequences have not been shown in detail in order not to obscure the invention. Those of ordinary skill in the art, with the included descriptions, will be able to implement appropriate functionality without undue experimentation.

Terms

[0028] References in the specification to“one embodiment,”“an embodiment,”“an example embodiment,” etc., indicate that the embodiment described may include a particular feature, structure, or characteristic, but every embodiment may not necessarily include the particular feature, structure, or characteristic. Moreover, such phrases are not necessarily referring to the same embodiment. Further, when a particular feature, structure, or characteristic is described in connection with an embodiment, it is submitted that it is within the knowledge of one skilled in the art to affect such feature, structure, or characteristic in connection with other embodiments whether or not explicitly described.

[0029] Bracketed text and blocks with dashed borders (e.g., large dashes, small dashes, dot- dash, and dots) may be used herein to illustrate optional operations that add additional features to embodiments of the invention. However, such notation should not be taken to mean that these are the only options or optional operations, and/or that blocks with solid borders are not optional in certain embodiments of the invention.

[0030] In the following description and claims, the terms“coupled” and“connected,” along with their derivatives, may be used. It should be understood that these terms are not intended as synonyms for each other.“Coupled” is used to indicate that two or more elements, which may or may not be in direct physical or electrical contact with each other, co-operate or interact with each other.“Connected” is used to indicate the establishment of communication between two or more elements that are coupled with each other.

[0031] The term“node” can be a network node/device that communicatively interconnects other electronic devices on the network (e.g., other network devices, end-user devices). Some network devices are“multiple services network devices” that provide support for multiple networking functions (e.g., routing, bridging, switching, Layer 2 aggregation, session border control, Quality of Service, and/or subscriber management), and/or provide support for multiple application services (e.g., data, voice, and video). Examples of network nodes also include NodeB, base station (BS), multi-standard radio (MSR) radio node such as MSR BS, eNodeB, gNodeB. MeNB, SeNB, integrated access backhaul (IAB) node, network controller, radio network controller (RNC), base station controller (BSC), relay, donor node controlling relay, base transceiver station (BTS), Central Unit (e.g., in a gNB), Distributed Unit (e.g., in a gNB), Baseband Unit, Centralized Baseband, C-RAN, access point (AP), transmission points, transmission nodes, RRU, RRH, nodes in distributed antenna system (DAS), core network node (e.g., MSC, MME, etc.), O&M, OSS, SON, positioning node (e.g., E-SMLC), etc.

[0032] Another example of a node is an end-user device, which is a non-limiting term and refers to any type of wireless and wireline device communicating with a network node and/or with another UE in a cellular/mobile/wireline communication system. Examples of end-user device are target device, device to device (D2D) user equipment (UE), vehicular to vehicular (V2V), machine type UE, MTC UE or UE capable of machine to machine (M2M)

communication, PDA, Tablet, mobile terminals, smart phone, laptop embedded equipment (LEE), laptop mounted equipment (LME), Internet-of-Things (IoTs) electronic devices, USB dongles, etc.

[0033] A node may be an endpoint node of a traffic flow (also simply referred to as“flow”) or an intermediate node (also referred to as an on-path node) of the traffic flow. The endpoint node of the traffic flow may be a source or destination node (or sender and receiver node, respectively) of the traffic flow, which is routed from the source node, passing through the intermediate node, and to the destination node. A flow may be defined as a set of packets whose headers match a given pattern of bits. A flow may be identified by a set of attributes embedded to one or more packets of the flow. An exemplary set of attributes includes a 5-tuple (source and destination IP addresses, a protocol type, source and destination TCP/UDP ports).

[0034] A node comprises an electronic device. An electronic device stores and transmits (internally and/or with other electronic devices over a network) code (which is composed of software instructions and which is sometimes referred to as computer program code or a computer program) and/or data using machine -readable media (also called computer-readable media), such as machine -readable storage media (e.g., magnetic disks, optical disks, solid state drives, read only memory (ROM), flash memory devices, phase change memory) and machine- readable transmission media (also called a carrier) (e.g., electrical, optical, radio, acoustical or other form of propagated signals - such as carrier waves, infrared signals). Thus, an electronic device (e.g., a computer) includes hardware and software, such as a set of one or more processors (e.g., of which a processor is a microprocessor, controller, microcontroller, central processing unit, digital signal processor, application specific integrated circuit (ASIC), field programmable gate array (FPGA), other electronic circuitry, a combination of one or more of the preceding) coupled to one or more machine -readable storage media to store code for execution on the set of processors and/or to store data. For instance, an electronic device may include non-volatile memory containing the code since the non-volatile memory can persist code/data even when the electronic device is turned off (when power is removed). When the electronic device is turned on, that part of the code that is to be executed by the processor(s) of the electronic device is typically copied from the slower non-volatile memory into volatile memory (e.g., dynamic random-access memory (DRAM), static random-access memory (SRAM)) of the electronic device. Typical electronic devices also include a set of one or more physical network interface(s) (NI(s)) to establish network connections (to transmit and/or receive code and/or data using propagating signals) with other electronic devices. For example, the set of physical NIs (or the set of physical NI(s) in combination with the set of processors executing code) may perform any formatting, coding, or translating to allow the electronic device to send and receive data whether over a wired and/or a wireless connection. In some embodiments, a physical NI may comprise radio circuitry capable of (1) receiving data from other electronic devices over a wireless connection and/or (2) sending data out to other devices through a wireless connection. This radio circuitry may include transmitter(s), receiver(s), and/or transceiver(s) suitable for radiofrequency communication. The radio circuitry may convert digital data into a radio signal having the proper parameters (e.g., frequency, timing, channel, bandwidth, and so forth). The radio signal may then be transmitted through antennas to the appropriate recipient(s). In some embodiments, the set of physical NI(s) may comprise network interface controller(s) (NICs), also known as a network interface card, network adapter, or local area network (LAN) adapter. The NIC(s) may facilitate in connecting the electronic device to other electronic devices allowing them to communicate with wire through plugging in a cable to a physical port connected to a NIC. One or more parts of an embodiment of the invention may be implemented using different combinations of software, firmware, and/or hardware.

[0035] QUIC is a general-purpose transport layer network protocol. While it may be referred to as the acronym for Quick User Datagram Protocol (UDP) Internet Connections, some organizations (e.g., Internet Engineering Task Force, IETF) refer to QUIC as the name of the protocol without treating it as an acronym. QUIC may be viewed as similar to Transmission Control Protocol (TCP) + enhancement such as Transport Layer Security (TLS) and/or

Flypertext Transfer Protocol 2.0 (HTTP/2 or HTTP/2.0) but implemented on UDP. QUIC is a UDP based stream-multiplexed and secure transport protocol with integrity protected header and encrypted payload. Yet unlike the traditional transport protocol stack with TCP (Transmission Control Protocol), which resides in the operating system kernel, QUIC can easily be implemented in the application layer. Consequently, this improves flexibility in terms of transport protocol evolution with implementation of new features, congestion control, deployability, and adoption. QUIC may use TLS for security handshake. TLS exchanges the necessary keying material in the protocol’s handshake. The use of TLS (defined in IETF Request for Comments (RFC) 8446) or Datagram TLS (DTLS) (under discussion, see IETF Internet-Draft draft-ietf-tls-dtls 13-31 dated March 25, 2019) is very common as a transport security solution independent from the transport protocol being TCP or UDP. Note that HTTP- over-QUIC is sometimes referred to as HTTP/3 as approved by IETF.

[0036] Address translation may be performed in a communications network. For example, Session Traversal Utilities for NAT (Network Address Translator) (STUN) is a standardized protocol on top of UDP used for Unilateral Self- Address Fixing (UNSAF), which is the process of determining what IP address and protocol port a particular traffic flow (also referred to as network flow) has on the external side of a Network Address Translator (NAT). STUN is defined in IETF Request for Comments (RFC) 5389, entitled“Session Traversal Utilities for NAT (STUN)” and dated October 2008. In a peer-to-peer environment, for UDP-based multimedia sessions, IETF RFC 5245, entitled“Interactive Connectivity Establishment (ICE): A Protocol for Network Address Translator (NAT) Traversal for Offer/ Answer Protocols” and dated April 2010, defines operations when there are network address translators on a path (also referred to as network/flow/traffic path) between two peers. ICE currently relies on STUN as a mechanism to determine the address that a traffic flow has in any specific address domain (e.g., internal or external by querying a STUN server in that address domain). The initial applications of QUIC are client-server centric, but QUIC is expected to be used in peer-to-peer environments as well. Thus, QUIC needs to define the operations about NATs on a network path in a peer-to- peer environment, similar to what ICE currently defines for the multimedia sessions.

Middlebox Address Translation

[0037] Figure 1 shows address translation in a communications networks according to some embodiments of the invention. A sender node (also referred to as sender, sending/initiating node, or flow initiator) 102 in the network 100 initiates communication to a receiver node (also referred to as receiver, receiving node, or flow destination) 104 by sending an IP packet with a transport protocol payload, e.g., UDP. This IP packet will be routed on a particular path through the network by routers (R) and middleboxes (M), as depicted in Figure 1. The sender 102 is the source node and the receiver 104 is the destination node of the IP packet. Both routers

(references 112, 114, 116, and 118) and middleboxes (Ml and M2 at references 122 and 124) are intermediate nodes on paths of the communications network, but the routers forward packets of traffic flows to their respective destinations while the middleboxes do more operations (e.g., insert/revise/remove information included in the packets).

[0038] This example path contains four regular routers (which do not change headers/trailers of an IP packet) and two middleboxes (which do). Ml is a Network Address Translator (NAT) that translates the local IP address of the sender 102 available in the IP source address field into an IP address associated with Ml’s external domain (in Figure 1 on the right side of Ml). M2 is a second NAT translating the source IP address provided by Ml into a different address provided by M2. Thus, the receiver 104 sees only the source address provided by M2.

[0039] A common embodiment of the NAT functionality creates a translation state for each flow identified by the 5-tuple (IP source and destination address, transport protocol, source and destination ports) on both its internal and external domains. Thus, it maintains a state for each flow so that it can map the addresses between the internal and external domains depending on which way packets belonging to the flow are travelling. The state information may include (1) a 5-tuple to 5-tuple mapping, (2) time of last packet of the flow, and (3) current connection state of the flow.

[0040] The connection state of a flow has different values depending on the protocol implementation. In the example of TCP, the connection state may be maintained by a TCP state machine. In one embodiment, the state machine starts with the client sending a connection request, e.g., a SYN packet, to the server, during which the initial three-way handshake takes place. After the three-way handshake is completed (seen by the server and by intermediary NATs), the TCP state machine moves to a so-called“established” state, with the connection then flow established. After data is transmitted, the same flow may enter a“closing” state when either endpoint, e.g., client or server, requests to close the connection by sending out a FIN packet. When the connection termination procedure is completed, the state machine may move to the “closed” state for a brief period (e.g., a few seconds) to let the binding (e.g., address/port translation) be removed. In the case of UDP, state may be based on heuristics such as whether there is a single initial burst or continuous transmission of packets, commonly applied by network devices (on the end-to-end path) that need to get some grip of UDP traffic, e.g., firewalls. The termination of a UDP flow may be based on timers, e.g., inactivity. Thus, in TCP, a connection state of a flow may be Initiating (e.g., SYN packet sent), Established, Closing, and Closed; and for UDP, the current connection state may be Initial, Existing, Terminating. For TCP, the connection state may be tracked as an indication of what packets to accept and what the current timeout should be.

[0041] This state information consumes some resources (e.g., lookups) and is therefore removed if there is no activity in the flow after some time. The length of the no activity timeout (e.g., measured from the time of the last packet of the flow), expiration of which causes the NAT to delete the flow state, is not fixed and protocol dependent (even though there exist recommendations) and usually implementation specific.

[0042] This example may demonstrate the functionality of embodiments of how middleboxes can securely communicate to the sender of the IP packets in a bi-directional flow between two peers. [0043] For example, a NAT that updates the source IP address and port numbers may signal the flow initiator (sender) about the values of the NAT’s operation. Optionally, the NAT can also sign the modified information to provide source authentication. For traffic flows, like QUIC or DTLS over UDP, this information can be encrypted to prevent on-path inspection and certain forms of tampering using the flow initiator’s keying material from the security handshake present in the UDP payload, e.g., QUIC or DTLS handshake.

[0044] Thus, each on-path node (e.g., a middlebox) that has some information to provide to the flow initiator may add its encrypted data object and optionally also its public key material and address information to the packet. The packet destination is not able to decrypt the data as the flow initiator’s key material is used to protect the data object. The packet receiver returns the received information to the flow initiator, either inside higher protocol functions or using the same or similar mechanism that has allowed the middleboxes to modify the packet in the forward path, e.g., UDP options or an IPv6 Destination Option (see IETF RFC 8200), as explained in more details herein below.

[0045] When the flow initiator receives the encrypted data objects it can decrypt them using the private key of its keying material. After this, the flow initiator can utilize the information as it sees fit. This provides a confidentiality protected way for an on-path node to provide information to the flow initiator. Fiowever, unless the information is cryptographically signed, and the identity is included with the information, there will not be source authenticity. A property of this solution is that removal or substitution of the whole data object (which is inserted by a middlebox) is a possibility.

[0046] In cases where the middleboxes have included their public key and addresses and that have reached the packet destination, the packet destination may initiate an encrypted communication with any of the middleboxes to explore more potential usage of them.

Options for Secured Communications Between Middlebox and Endpoint Nodes

[0047] A requirement for a middlebox to communicate securely with an endpoint node is that the IP packet or the transport protocol transmitted in the IP packet is used in a way that enables an on-path extension of the packet or usage of a reserved area in the IP packet’s or transport protocol’s header/trailer where the middleboxes can write information. The information needs to fit within the provided reserved area or the extra needed space should not exceed the Maximum Transmission Unit (MTU) of the network to avoid fragmentation. UDP Options and IPv6 Destination Header Extensions are two potential options.

UDP Options

[0048] Using UDP Options allows for multiple defined options to be added after the UDP data payload but before the end of the IP packet. The presence of UDP options are detected when the UDP packet length field does not consume all remaining space in the IP packet. For some embodiments, to use the UDP options, a new UDP option to carry the protected information needs to be defined. It would also require a change to the proposed rule disallowing any changes to the UDP options part in flight. A new option would require that a format is defined.

[0049] Figure 2A shows implementing UDP Options for secured communications between middlebox and endpoint nodes according to some embodiments of the invention. In Figure 2A, an IP packet encapsulates a UDP datagram. The IP packet includes an IP header 252 and an IP transport payload. The IP transport payload includes an UDP header 254 and UDP user data 256 of the encapsulated UDP datagram. The UDP length 264 is made less than the IP transport payload length 262, and the difference is used to accommodate surplus data 258 (which may be referred to as a UDP trailer).

[0050] The surplus data 258 may be used to implement UDP options. In one embodiment, the surplus data 258 starts with the options type (KIND) 220 and length (LEN) fields 222, and followed by a value field 290, which may include information object 210 and optionally reserved space for additional information objects 212. The value (data) field of the option contains zero, one, or more information objects 210 added by the packet sender or middlebox.

To avoid packet expansion, the packet sender may include unused space in the option’s value field, which is reserved for additional information objects that may be added by middleboxes on the path.

[0051] Figure 2B shows an exemplary information object within an UDP option’s value field according to some embodiments of the invention. The information object 210 itself follows a Type Length Value (TLV) structure. The length of protected data 202 identifies the length of information object 210, the type identifies a protection profile 204, and the protected data 206 includes the information/data to be protected. The protection profile 204 may refer to how (in which format) the data part is protected. For example, the protection profile 204 may include static parameters such as the encryption algorithms (or more broadly, cryptographic algorithm) to be used for encryption, lengths of encryption keys, and where in the data part any additional information need for decryption would be at.

[0052] In some embodiments, while protection profile 204 may include static information that is pre-configured, the protected data 206 may include dynamic information generated through encryption. In these embodiments, the protected data 206 may include the encrypted information and the information necessary to decrypt the information encrypted by a middlebox. The protected data 206 may also include a signature over the protected data, the format of the signature, and location of the signature specified by the profile. Figure 2C shows an exemplary structure of protected data according to some embodiments of the invention. The protected data 206 comprises a key identifier 280 to enable the sender to retrieve a private key sk, a key encapsulation cjcem 282, a data encapsulation c_dem 284, a certificate (e.g., one provided by a middlebox) 286, and a signature 288 made with the public key in the certificate (e.g., the signature may be made with a private key associated with the public key in an asymmetric key pair). The key identifier 280 is optional as the sender may find the secret key in an alternative way. The key encapsulation 282 may include other information such as an algorithm identifier and random number. The data encapsulation 284 is the ciphertext resulting from encrypting the cleartext data that the middlebox provides (e.g., the cleartext data 300 discussed herein below). The data encapsulation 284 may include other information such as an integrity tag, algorithm identifier, random number, etc. The certificate 286 and signature 288 are optional and sent to use in cases where the middlebox authenticates the protected data.

[0053] In some embodiments, the protection profile 204 may include the information necessary to decrypt the information encrypted by the middlebox while the protected data 206 includes only the encrypted information. In these embodiments, the key identifier 280, the key encapsulation 282, certificate 286, and signature 288 are stored in the protection profile 204 while the data encapsulation 284 is stored in the protected data 206. Other embodiments may store in the protection profile 204 a portion of the information necessary to decrypt the information encrypted by the middlebox, and the remaining portion in the protected data 206 along with the data encapsulation 284. Embodiments of the invention may implement various distributions of the information to decrypt and the encrypted information between the protection profile 204 and protected data 206.

[0054] Figure 3A shows an exemplary cleartext data object generated by a middlebox according to some embodiments of the invention. The cleartext data 300 is a data object for IPv4 translation record. The data object starts with type field 302 that identifies the format of the data, in this case an IPv4 NAT translation record. The translation record contains a duration of the timeout used, as indicated in a state minimal lifetime timer field 304. It identifies the transport protocol translated, as indicated in transport protocol field 306, so the correct 5-tuple can be identified. It may also include a source/destination field 308 indicating whether the source or destination fields are being translated for the data object. The data object also includes original and new IPv4 addresses 312 and 314, respectively, and the corresponding fields for ports at references 316 and 318, respectively. The cleartext data may be encrypted within the data encapsulation 284 of the protected data 206 shown above.

[0055] At the receiving node of the IP packet, since the length of the protected data 206 is indicated in the information object 210, the receiving node will be able to find the next data object when multiple ones are concatenated one after another. The receiving node will also be able to identify both the cipher suit applied to protect the type and data parts by examining the protection profile 204 and protected data 206.

[0056] Figure 3B shows information included in another cleartext data object generated by a middlebox according to some embodiments of the invention. The cleartext data object may take the structure similar to the one shown in Figure 3A, and it includes discovery information for the traffic flow. The discovery information is explained in more details in a co-pending international application, entitled“Method and System for In-band Signaling in a QUIC Session,” which is incorporated by reference herein in its entirety for all purposes. The discovery information may include two sets of information - identification 352 and features/functions 354 supported by the middlebox node.

[0057] The identification information 352 may include one or more of the middlebox node’s global identifier or common name (CNAME), its node certificate, and optionally its IP address and/or port.

[0058] The features/functions 354 may contain a list of different features/functions the middlebox node is able to perform along with the information required to perform those functions. The sender node can then decide what function it allows the middlebox node to perform and exposes that information to the middlebox node. The feature/function part can also include a link to the detailed list of features. For example, the features/function may include the following:

(1) congestion control enhancement function/feature (request information: ACK, which notifies the sender node that the middlebox node needs to have access to an acknowledge frame to perform the improvement);

(2) a split or domain specific congestion control function/feature (request information: ACK);

(3) a traffic exposure function/feature (request information: statistics, reports with destinations). Traffic exposure may include Quality of Experience (QoE) metrics supplied from a client to the network (e.g., collected by a middlebox node), it could be information exposed from the network to the application such as subscriber quota status, policy requirements, etc. The statistics and reports include, for example, a video client supplying Media Object Server (MOS) data to the network via the middlebox node; and the middlebox node supplies network level statistics to an application, e.g., type of access network, throughput experienced by a user equipment (UE) over a period (e.g., last number of seconds); and

(4) a link to a more detailed set of function/feature list (e.g., a FiTTPS link).

[0059] The sender and middlebox node will agree on the feature usage. The encryption of the middlebox packets may use the encryption algorithms described herein. [0060] Thus, a middlebox node may generate a translation record, feature support information, and other traffic flow information to be protected as protected data (e.g., protected data 206) in a protection envelope and transmit it to the receiver node, which may decrypt the traffic flow information and/or transmit the protected data to the sender node to decrypt as discussed herein.

IPv6 Destination Header Extension

[0061] Other than the UDP options, an IPv6 Destination Header Extension is another alternative for a general mechanism not coupled to a specific transport protocol. The Destination Options are intended to be read by the destination (the receiving node of an IP packet) and that matches the intention of securely exchanging information between the middlebox and end nodes perfectly. Figure 4 shows implementing IPv6 Destination Header Extension for secured communications between middlebox and endpoint nodes according to some embodiments of the invention.

[0062] The main IPv6 header 490 includes a version field 402, a traffic class field 404, a flow label field 406, a payload length field 412, a next header field 414, a hop limit field 415, a source address field 420, and a destination address field 422. These fields are defined in standards such as IETF RFC 8200.

[0063] A number of IPv6 header extensions may follow the main Ipv6 header 490. Each option is indicated through the Next Header field in the previous option or main header (e.g., the next header field 414 may indicate the existence of a destination options header). Each header extension may have a length field to indicate the length of the actual header extension. A destination Options Header 450 may be added by the IP packet sender or an on-path node (e.g., sender 102 or middlebox 122/124). The destination Options Header 450 includes a next header 460 (indicating whether or not the next item is an upper-layer header) and a header extension length 462 (indicating the length of the current header) in one embodiment.

[0064] For example, an IP packet sender (e.g., sender 102) may add a destination options header with some amount of reserved space for middleboxes to add their secured information objects. This has the additional benefit of avoiding packet expansion issues that could cause an IPv6 packet to exceed the path MTU due to middleboxes adding too many information objects. In this embodiment, the IP packet sender may add the destination header extension for protected information from middleboxes with an assigned type identifier and a length field corresponding to the chosen amount of space. The data space is then filled with the length field number of bytes of value zero to enable anyone to identify an added data object in one embodiment.

[0065] In one embodiment, a middlebox that wants to add a data object to an IP packet received from the IP packet sender would look at first bytes matching the length field of the reserved area, and if zero it can then write its data object (for example, following the Length- Protection Profile-Information Object format in Figure 2B) into the reserved area, assuming it fits. If the beginning of the reserved area contains a non-zero value, the middlebox interprets this as a data object and jumps to the area within the header after it to check if there are additional objects. If there are no additional objects and the remaining space is sufficient, the middlebox adds its object. The added object may take the structure as explained in Figure 2B, e.g., including the information object 210 and/or reserved space for additional information objects 212.

Alternative Embodiments to Protect Data

[0066] While an information object may be protected using structures discussed herein above, Figure 5 shows a protection envelope that would allow for adding various cleartext data entries according to some embodiments of the invention. The protection envelope 500 may be implemented using UDP Options (e.g., in the surplus data 258) or IPv6 Destination Header Extension (e.g., in Destination Options Header 450) as discussed herein. Each entry may be a type/length/value (TLV) structure, thus allowing middleboxes and endpoints to skip to the next TLV even if a type of a TLV is unknown. This could, for example, provide any other middlebox node on the path or the packet destination with the address of the middlebox to add a data object or entity.

[0067] Figure 5 shows the format with a one-bit indicator (E) 502 if any extension TLVs in cleartext is present, else only the protected data. For example, E = 0 may indicate no TLV structure at all, only the protected data 536 itself; while E = 1 indicates the presence of one or more TLVs, and one of the TLVs may be the TLV for the protected data 536 (i.e., the TLV having type 532, length 534 and value 536). Other ways of using one or more bits of TLV indication are also viable. The length field following the E bit is the length of the whole entry 504, allowing one or more middleboxes that simply need to find the next entry to skip the internal structure. A middlebox may insert each TLV as needed. In this example, the cleartext TLVs 550 include one for IPv4 address (e.g., a new IP address after NAT) (i.e., fields 512, 514, 516) and one for identity data (e.g., the identity of the middlebox providing the data within the protection envelope 500) (i.e., fields 522, 524, 526). The protection profile 506 may serve the same/similar function as the protection profile 204; and the protected data 536 may serve the same/similar function as protected data 206, which is included in the TLV after the cleartext TLVs 550 in this example.

Encryption and Integrity Verification

[0068] A middlebox that wants to provide information to the IP flow sender may need to acquire the keying material necessary to secure the communication of the information. Unless the flow sender can be identified and there already are provisioned security material that the middlebox knows, the keying material is acquired from the higher layer security establishment (e.g., TLS) that the sender performs in this IP flow.

[0069] In cases where the sender establishes secure communication with the corresponding receiver using protocols with in-band handshake, where keying material is transferred such as DTLS, TLS, and/or QUIC, a middlebox can capture this keying material and associate it with the rest of its flow specific state, e.g., forming a 6-tuple. The additional information in the 6- tuple may be the keying materials, which provide the security context information, and the keying materials/security context information may be retained for later use also. The keying material in the handshake message from the sender contains at least one public key. The middlebox uses one of the public keys to encrypt information. In one embodiment, the following operations are performed:

[0070] (1) The sender has a one or more key pairs (pk , sk) and includes at least one public key pk in the handshake message. The key pairs may be static or ephemeral, e.g., ephemeral Diffie- Hellman key pairs. The handshake message may also contain other information such as algorithm identifiers, random numbers, etc. The information in the handshake message may be exposed to a middlebox, where no prior association exists. When the two peers (the sender and receiver) have talked before, the peers’ public keys are known, and protection may be performed using the peer’s public key. When the middlebox protects the data using the receiver’s public key, the receiver may decrypt the protected data, and the receiver may echo the information back to the sender utilizing another protection mechanism or unprotected.

[0071] (2) The middlebox chooses one of these public keys and encrypts the information m using public-key encryption and attaching c = Enc(m, pk) to the message (where“Enc” denotes encryption). The information m may include the translation records such as the ones shown in Figure 3A. The middlebox also optionally includes its own public key and address information. The middlebox may use other information such as algorithm identifiers, random numbers, etc. to encrypt the message. The middlebox may attach other information such as an algorithm identifier, random number, etc. to the message. Additionally, the middlebox may attach additional information (e.g., sender identity) necessary for a decrypting party to decrypt.

[0072] (3) The sender decrypts the information m = Dec(c, sk) to retrieve the information m

(where“Dec” denotes decryption), once the information is transmitted by the receiver, which receives the information from the middlebox. The sender may use other information such as algorithm identifiers, random numbers, etc. to decrypt the message.

[0073] (4) Optionally, the receiver (the packet destination) may use the middlebox’ s public key and address information (if any) to establish a secure connection to the middlebox for further communication. [0074] The public key encryption algorithm may be a so-called hybrid encryption algorithm (e.g., Elliptic Curve Integrated Encryption Scheme (ECIES)) comprising of a key encapsulation mechanism and a data encapsulation mechanism. The public key encryption algorithm could also be a non-hybrid public key encryption mechanism such as RSAES-PKCSl-vl_5, RSAES- OAEP, as explained in IETF RFC 8017. The following example is based on the hybrid public key mechanism; however, embodiments of the invention can be generically applied to encryption using non-hybrid mechanisms.

[0075] When a hybrid encryption algorithm is used, the key encapsulation mechanism can be selected from a group including finite field, elliptic curve Diffie-Hellman, and Post-Quantum Algorithms such as SIKE, Kyber, NewHope, and Frodo. The data encapsulation algorithms can be encryption algorithms such as AES-CTR, AES-GCM, ChaCha20-PoIyl305, or AES-CTR + HMAC-SHA256 and may also protect the integrity of the whole or part of the information and optional Additional Authenticated Data (AAD).

[0076] In the embodiment with a hybrid encryption algorithm, the middlebox may use a Key Encapsulation Mechanism (KEM) ( c_kem , k) = KEM_Encaps(pk) to create an encapsulation cjcem and a shared secret k. The middlebox then may use a Data Encapsulation Mechanism (DEM) c_dem = DEM_Encaps(r/k, m) to encrypt the information m with the key dk. The key dk is a function of the shared secret k, i.e., using a Key Derivation Function (KDF) such that dk = KDF(k, additional parameters). The middlebox attaches c = (cjcem, c_dem ) to the message. The sender may then use the corresponding key decapsulation algorithm k = KEM_Dccaps(.sk, cjcem ) to retrieve the shared secret k and use the corresponding data decapsulation algorithm m = DEM_Decaps(¾ c_dem ) to decrypt the information m, where both KEM_Decaps and DEM_Decaps refer to KEM and DEM decapsulation.

[0077] In the embodiment with finite-field Diffie-Hellman, the sender would have the key pair ( pk = g , sk = x ), and the key encapsulation mechanisms would be ( cjcem = g ^z , k = ¹² ) = KEM_Encaps(pk = g ¹ ) and k = g ^xz = KEM_Dccaps(.sk = x, cjcem = g ^z ).

[0078] This mechanism is then used to encrypt any information object that the middlebox wants to attach to the IP packet using a suitable and identified encryption algorithm. Depending on the encryption algorithm, the information object and other additional information (that may or may not be sent in the packet) may be integrity protected. The information object may be of various kinds but to be used in the aforementioned case with NATs as illustrated in Figure 1. For example, Ml could provide the address translation it performs, i.e., the change to the source IP address and port. It can also include its NAT state timer duration for the flow, thus ensuring that the sender knows how often it needs to refresh the flow state by sending keep-alive messages during any longer periods of inactivity. The sender can also use the shared secret k (k = g* ^z in the embodiment with finite -field Diffie-Hellman) to enable secured communication towards the middlebox. The middlebox and the destination of the IP packet (the receiver) can also exchange a shared secret to enable secured communication between them. In this case, the middlebox and receiver will have another set of key pairs (pk = g ^z , sk = z), where g ^z is a public key provided by the middlebox and g ^y is a public key provided by the receiver. The key encapsulation mechanism would be ( c_kem = g ^z , k = g ^yz ) = KEM_Encaps(pk = g ^y ) and k = g ^yz =

KEM_Dccaps(.sk = y, cjcem = g ^z ).

[0079] The exchange information and mechanism can then be used to encrypt any information object within a packet for an IP flow destination (i.e., the receiver 104 in Figure 1), would like to attach to any subsequent IP packets towards the sender with the intention to be intercepted by the middlebox or directly addressed. For example, the receiver might query the full range of features supported by the middlebox and then the receiver can instruct or give consent to the sender to use all or some of the features provided by the middlebox.

[0080] The encryption and integrity verification do not provide any source authentication in one embodiment. That could be optionally provided by the middlebox in an alternative embodiment by it signing the information using its signature and attaching an identity assertion of the middlebox. However, numerous applications of this method would achieve benefits even without such assertions.

[0081] The identity assertion may be a certificate or a certificate chain. Instead of an identity assertion, the middlebox may attach an identifier for the identity assertion, such an identifier may, for example, be a hash or an URL. The identity assertion may be encoded in the signature, a so-called implicit certificate. The signature algorithm used may be independent of the public key encryption algorithm. The middlebox may use information in the handshake message to select a signature algorithm and identity assertion that the sender can verify. The signature algorithm can for example be RSASSA-PSS, RSASSA-PKCSl-vl_5, DSA, Elliptic Curve Digital Signature Algorithm (ECDSA), Edwards-curve Digital Signature Algorithm (EdDSA), or a Post-Quantum Signature Algorithm such as DILITHIUM, qTESLA, Rainbow, or

SPHINCS+. The Post-Quantum signature algorithms are going through a standardization effort led by the National Institute of Standards and Technology (NIST), and the algorithms under consideration by the NIST as of 2019 are included in the Post-Quantum Cryptography (PQC) Round Two candidates. Embodiments of the invention may utilize one or more of the candidates.

[0082] Middleboxes that maintain flow state usually do so via some form of soft state based on flow activity that can store the keying material and other encryption related information in its state, while the flow state exists, and then remove that at the same time the other flow state is destroyed. This enables a middlehox to attach information to any flow related packet, also after the initial security handshake between the flow initiator and the receiver.

Some Embodiments

[0083] The operations in the flow diagrams will be described with reference to the exemplary embodiments of the other figures. However, it should be understood that the operations of the flow diagrams can be performed by embodiments of the invention other than those discussed with reference to the other figures, and the embodiments of the invention discussed with reference to these other figures can perform operations different than those discussed with reference to the flow diagrams.

[0084] Figure 6 is a flow diagram illustrating the operations at a network device that is on a path between a source network device and destination network device according to some embodiments of the invention. The network device may comprise a middlehox node M1/M2 at references 122/124 of Figure 1, where an IP packet is transmitted from a source network device (the sender 102) toward a destination network device (the receiver 104), and the network device is on the path of a traffic flow from the source network device to destination network device. At reference 602, the network device receives an IP packet of a traffic flow, where the IP packet includes a transport protocol (e.g., TCP/UDP) payload. The traffic flow may be identified by a 5-tuple as discussed above.

[0085] At reference 604, the network device inserts traffic flow information into the IP packet, wherein the network device encrypts the traffic flow information prior to the inserting. The traffic flow information may include network address translation information and/or discovery information discussed herein. At reference 606, the network device transmits the IP packet after the inserting toward the destination network device, wherein the IP packet after the inserting includes the encrypted traffic flow information and encryption information to allow another network device to decrypt the encrypted traffic flow information. The encrypted traffic flow information and encryption information to allow another network device to decrypt may be stored in structures discussed herein above relating to Figures 2A-C, 3A-B, and 4-5.

[0086] The traffic flow information may include state information of a traffic flow (e.g., (1) a 5-tuple to 5-tuple mapping, (2) time of last packet of the traffic flow, and (3) current connection state of the flow as discussed herein above). The traffic flow information may also include other information such as the discovery information discussed relating to Figure 3B.

[0087] The encryption uses a public key of the source network device in one embodiment. In one embodiment, the network device obtains keying materials for the encryption from the source network device or destination network device. In one embodiment, the state information includes address translation mapping and/or port translation mapping as shown in Figure 3A boxes 312, 314, 316, 318. In one embodiment, the state information includes a field indicating whether source or destination network device information is included in the state information as shown in Figure 3A in box 308.

[0088] In one embodiment, the state information is inserted within a UDP options field. In one embodiment, the state information is inserted as an IPv6 header extension.

[0089] In one embodiment, the network device includes its key information, identity, or key information and identity in the IP packet. In one embodiment, the network device includes one or more type length value (TLV) structures when updating the IP packet as shown in Figure 4, reference 450. In one embodiment, the network device signs the updated IP packet and/or attaches an identity assertion prior to sending the updated IP packet. For example, the encryption information to allow another network device to decrypt may include at least one of the signatures of the network device, an identity assertion by the network device, or any combination thereof.

[0090] Figure 7 is a flow diagram illustrating the operations at a destination network device of a path from a source network device, passing through an intermediate network device, to the destination network device according to some embodiments of the invention. At reference 702, the network device receives an IP packet of a traffic flow, where the IP packet includes a transport protocol (e.g., TCP/UDP) payload. The traffic flow may be identified by 5-tuple as discussed above.

[0091] At reference 704, the network device identifies information inserted by the

intermediate network device from the IP packet. At reference 706, the network device communicates with the source network device or the intermediate network device based on the identified information.

[0092] In one embodiment, the information inserted by the intermediate network device comprises the inserted information as discussed relating to Figure 6.

[0093] In one embodiment, the destination network device transmits at least a portion of the inserted information to the source network device at reference 712. For example, the inserted information includes the protected data discussed herein above and the protected data is transmitted to the source network device. In one embodiment, the destination network device establishes encrypted communication with the intermediate network device at reference 714 when the inserted information includes key information of the intermediate network device.

[0094] Figure 8 is a flow diagram illustrating the operations at a source network device of a path from the source network device, passing through an intermediate network device, and for a destination network device according to some embodiments of the invention. At reference 802, the network device transmits a first IP packet of a traffic flow, where the IP packet includes a transport protocol (e.g., TCP/UDP) payload. The traffic flow may be identified by 5-tuple as discussed above.

[0095] At reference 804, the network device identifies information inserted by the intermediate network device (e.g., a middlebox) from a second IP packet sourced from the destination network device that receives the first IP packet. The destination network device extracts the information inserted by the intermediate network device, e.g., the protected data, from the first IP packet received by the destination network device and inserts the information into the second IP packet in one embodiment. At reference 806, the network device establishes encrypted communication with the intermediate network device using the information inserted by the intermediate network device.

[0096] The embodiments of the invention provide an encrypted and potentially authenticated signaling, i.e., an explicit communication channel from a middlebox node to an endpoint node, e.g., the sender 102 or receiver 104, that initiates a secured communication session using a protocol that carries public key material.

[0097] The embodiments of the invention enable the middlebox to include sensitive information to packets, as the sensitive information cannot be accessed by other on-path nodes nor any of the endpoints unless the endpoints have the secrets associated with the public key material.

Network Environments Under Which Embodiments of the Invention May Operate

[0098] Figure 9A illustrates connectivity between network devices (NDs) within an exemplary network, as well as three exemplary implementations of the NDs, according to some embodiments of the invention. Figure 9A shows NDs 900A-H, and their connectivity by way of lines between 900A-900B, 900B-900C, 900C-900D, 900D-900E, 900E-900F, 900F-900G, and 900A-900G, as well as between 900FI and each of 900A, 900C, 900D, and 900G. These NDs are physical devices, and the connectivity between these NDs can be wireless or wired (often referred to as a link). An additional line extending from NDs 900A, 900E, and 900F illustrates that these NDs act as ingress and egress points for the network (and thus, these NDs are sometimes referred to as edge NDs; while the other NDs may be called core NDs).

[0099] Two of the exemplary ND implementations in Figure 9 A are: 1) a special-purpose network device 902 that uses custom application-specific integrated-circuits (ASICs) and a special-purpose operating system (OS); and 2) a general purpose network device 904 that uses common off-the-shelf (COTS) processors and a standard OS.

[00100] The special-purpose network device 902 includes networking hardware 910 comprising a set of one or more processor(s) 912, forwarding resource(s) 914 (which typically include one or more ASICs and/or network processors), and physical network interfaces (NIs) 916 (through which network connections are made, such as those shown by the connectivity between NDs 900A-H), as well as non-transitory machine readable storage media 918 having stored therein networking software 920. During operation, the networking software 920 may be executed by the networking hardware 910 to instantiate a set of one or more networking software instance(s) 922. Each of the networking software instance(s) 922, and that part of the networking hardware 910 that executes that network software instance (be it hardware dedicated to that networking software instance and/or time slices of hardware temporally shared by that networking software instance with others of the networking software instance(s) 922), form a separate virtual network element 930A-R. Each of the virtual network element(s) (VNEs) 930A- R includes a control communication and configuration module 932A-R (sometimes referred to as a local control module or control communication module) and forwarding table(s) 934A-R, such that a given virtual network element (e.g., 930A) includes the control communication and configuration module (e.g., 932A), a set of one or more forwarding table(s) (e.g., 934A), and that portion of the networking hardware 910 that executes the virtual network element (e.g., 930A). In one embodiment, the networking software 920 comprises a middlebox to endpoint information exchange coordinator (MEIEC) 955, which performs operations discussed herein above. For example, when network device 902 serves as an intermediate network device on a path between a source network device and a destination network device, MEIEC 955 performs operations relating to Figure 6; when it serves as the destination network device, it performs operations relating to Figure 7; and when it serves as the source network device, it performs operations relating to Figure 8.

[00101] The special-purpose network device 902 is often physically and/or logically considered to include: 1) a ND control plane 924 (sometimes referred to as a control plane) comprising the processor(s) 912 that execute the control communication and configuration module(s) 932A-R; and 2) a ND forwarding plane 926 (sometimes referred to as a forwarding plane, a data plane, or a media plane) comprising the forwarding resource(s) 914 that utilize the forwarding table(s) 934A-R and the physical NIs 916. By way of example, where the ND is a router (or is implementing routing functionality), the ND control plane 924 (the processor(s) 912 executing the control communication and configuration module(s) 932A-R) is typically responsible for participating in controlling how data (e.g., packets) is to be routed (e.g., the next hop for the data and the outgoing physical NI for that data) and storing that routing information in the forwarding table(s) 934A-R, and the ND forwarding plane 926 is responsible for receiving that data on the physical NIs 916 and forwarding that data out to the appropriate ones of the physical NIs 916 based on the forwarding table(s) 934A-R. [00102] Figure 9B illustrates an exemplary way to implement the special-purpose network device 902 according to some embodiments of the invention. Figure 9B shows a special-purpose network device including cards 938 (typically hot pluggable). While in some embodiments the cards 938 are of two types (one or more that operate as the ND forwarding plane 926

(sometimes called line cards), and one or more that operate to implement the ND control plane 924 (sometimes called control cards)), alternative embodiments may combine functionality onto a single card and/or include additional card types (e.g., one additional type of card is called a service card, resource card, or multi-application card). A service card can provide specialized processing (e.g., Layer 4 to Layer 7 services (e.g., firewall, Internet Protocol Security (IPsec), Secure Sockets Layer (SSL) / Transport Layer Security (TLS), Intrusion Detection System (IDS), peer-to-peer (P2P), Voice over IP (VoIP) Session Border Controller, Mobile Wireless Gateways (Gateway General Packet Radio Service (GPRS) Support Node (GGSN), Evolved Packet Core (EPC) Gateway)). By way of example, a service card may be used to terminate IPsec tunnels and execute the attendant authentication and encryption algorithms. These cards are coupled together through one or more interconnect mechanisms illustrated as backplane 936 (e.g., a first full mesh coupling the line cards and a second full mesh coupling all of the cards).

[00103] Returning to Figure 9A, the general-purpose network device 904 includes hardware 940 comprising a set of one or more processor(s) 942 (which are often COTS processors) and physical NIs 946, as well as non-transitory machine -readable storage media 948 having stored therein software 950. During operation, the processor(s) 942 execute the software 950 to instantiate one or more sets of one or more applications 964A-R. While one embodiment does not implement virtualization, alternative embodiments may use different forms of virtualization. For example, in one such alternative embodiment the virtualization layer 954 represents the kernel of an operating system (or a shim executing on a base operating system) that allows for the creation of multiple instances 962A-R called software containers that may each be used to execute one (or more) of the sets of applications 964A-R; where the multiple software containers (also called virtualization engines, virtual private servers, or jails) are user spaces (typically a virtual memory space) that are separate from each other and separate from the kernel space in which the operating system is run; and where the set of applications running in a given user space, unless explicitly allowed, cannot access the memory of the other processes. In another such alternative embodiment the virtualization layer 954 represents a hypervisor (sometimes referred to as a virtual machine monitor (VMM)) or a hypervisor executing on top of a host operating system, and each of the sets of applications 964A-R is run on top of a guest operating system within an instance 962A-R called a virtual machine (which may in some cases be considered a tightly isolated form of software container) that is run on top of the hypervisor - the guest operating system and application may not know they are running on a virtual machine as opposed to running on a“bare metal” host electronic device, or through para-virtualization the operating system and/or application may be aware of the presence of virtualization for optimization purposes. In yet other alternative embodiments, one, some or all of the applications are implemented as unikernel(s), which can be generated by compiling directly with an application only a limited set of libraries (e.g., from a library operating system (LibOS) including drivers/libraries of OS services) that provide the particular OS services needed by the application. As a unikernel can be implemented to run directly on hardware 940, directly on a hypervisor (in which case the unikernel is sometimes described as running within a LibOS virtual machine), or in a software container, embodiments can be implemented fully with unikernels running directly on a hypervisor represented by virtualization layer 954, unikernels running within software containers represented by instances 962A-R, or as a combination of unikernels and the above-described techniques (e.g. , unikernels and virtual machines both run directly on a hypervisor, unikernels and sets of applications that are run in different software containers). Note that the networking software 950 comprises the middlebox to endpoint information exchange coordinator (MEIEC) 955, whose operations are discussed herein relating to the network device 902.

[00104] The instantiation of the one or more sets of one or more applications 964A-R, as well as virtualization if implemented, are collectively referred to as software instance(s) 952. Each set of applications 964A-R, corresponding virtualization construct (e.g., instance 962A-R) if implemented, and that part of the hardware 940 that executes them (be it hardware dedicated to that execution and/or time slices of hardware temporally shared), forms a separate virtual network element(s) 960A-R.

[00105] The virtual network element(s) 960A-R perform similar functionality to the virtual network element(s) 930A-R - e.g., similar to the control communication and configuration module(s) 932A and forwarding table(s) 934A (this virtualization of the hardware 940 is sometimes referred to as network function virtualization (NFV)). Thus, NFV may be used to consolidate many network equipment types onto industry standard high-volume server hardware, physical switches, and physical storage, which could be located in Data centers, NDs, and customer premise equipment (CPE). While embodiments of the invention are illustrated with each instance 962A-R corresponding to one VNE 960A-R, alternative embodiments may implement this correspondence at a finer level granularity (e.g., line card virtual machines virtualize line cards, control card virtual machine virtualize control cards, etc.); it should be understood that the techniques described herein with reference to a correspondence of instances 962A-R to VNEs also apply to embodiments where such a finer level of granularity and/or unikernels are used.

[00106] In certain embodiments, the virtualization layer 954 includes a virtual switch that provides similar forwarding services as a physical Ethernet switch. Specifically, this virtual switch forwards traffic between instances 962A-R and the physical NI(s) 946, as well as optionally between the instances 962A-R; in addition, this virtual switch may enforce network isolation between the VNEs 960A-R that by policy are not permitted to communicate with each other (e.g., by honoring virtual local area networks (VLANs)).

[00107] The third exemplary ND implementation in Figure 9A is a hybrid network device 906, which includes both custom ASICs/special-purpose OS and COTS processors/standard OS in a single ND or a single card within an ND. In certain embodiments of such a hybrid network device, a platform VM (i.e., a VM that that implements the functionality of the special-purpose network device 902) could provide for para-virtualization to the networking hardware present in the hybrid network device 906.

[00108] Regardless of the above exemplary implementations of an ND, when a single one of multiple VNEs implemented by an ND is being considered (e.g., only one of the VNEs is part of a given virtual network) or where only a single VNE is currently being implemented by an ND, the shortened term network element (NE) is sometimes used to refer to that VNE. Also in all of the above exemplary implementations, each of the VNEs (e.g., VNE(s) 930A-R, VNEs 960A-R, and those in the hybrid network device 906) receives data on the physical NIs (e.g., 916, 946) and forwards that data out the appropriate ones of the physical NIs (e.g., 916, 946). For example, a VNE implementing IP router functionality forwards IP packets on the basis of some of the IP header information in the IP packet; where IP header information includes source IP address, destination IP address, source port, destination port (where“source port” and“destination port” refer herein to protocol ports, as opposed to physical ports of a ND), transport protocol (e.g., user datagram protocol (UDP), Transmission Control Protocol (TCP), and differentiated services code point (DSCP) values.

[00109] Figure 9C illustrates various exemplary ways in which VNEs may be coupled according to some embodiments of the invention. Figure 9C shows VNEs 970A.1-970A.P (and optionally VNEs 970A.Q-970A.R) implemented in ND 900A and VNE 970H.1 in ND 900H. In Figure 9C, VNEs 970A.1-P are separate from each other in the sense that they can receive packets from outside ND 900 A and forward packets outside of ND 900 A; VNE 970 A.1 is coupled with VNE 970H.1, and thus they communicate packets between their respective NDs; VNE 970A.2-970A.3 may optionally forward packets between themselves without forwarding them outside of the ND 900 A; and VNE 970A.P may optionally be the first in a chain of VNEs that includes VNE 970A.Q followed by VNE 970A.R (this is sometimes referred to as dynamic service chaining, where each of the VNEs in the series of VNEs provides a different service - e.g., one or more layer 4-7 network services). While Figure 9C illustrates various exemplary relationships between the VNEs, alternative embodiments may support other relationships (e.g., more/fewer VNEs, more/fewer dynamic service chains, multiple different dynamic service chains with some common VNEs and some different VNEs).

[00110] The NDs of Figure 9A, for example, may form part of the Internet or a private network; and other electronic devices (not shown; such as end user devices including workstations, laptops, netbooks, tablets, palm tops, mobile phones, smartphones, phablets, multimedia phones, Voice Over Internet Protocol (VOIP) phones, terminals, portable media players, GPS units, wearable devices, gaming systems, set-top boxes, Internet enabled household appliances) may be coupled to the network (directly or through other networks such as access networks) to communicate over the network (e.g., the Internet or virtual private networks (VPNs) overlaid on (e.g., tunneled through) the Internet) with each other (directly or through servers) and/or access content and/or services. Such content and/or services are typically provided by one or more servers (not shown) belonging to a service/content provider or one or more end user devices (not shown) participating in a peer-to-peer (P2P) service, and may include, for example, public webpages (e.g., free content, store fronts, search services), private webpages (e.g., username/password accessed webpages providing email services), and/or corporate networks over VPNs. For instance, end user devices may be coupled (e.g., through customer premise equipment coupled to an access network (wired or wirelessly)) to edge NDs, which are coupled (e.g., through one or more core NDs) to other edge NDs, which are coupled to electronic devices acting as servers. However, through compute and storage virtualization, one or more of the electronic devices operating as the NDs in Figure 9A may also host one or more such servers (e.g., in the case of the general purpose network device 904, one or more of the software instances 962A-R may operate as servers; the same would be true for the hybrid network device 906; in the case of the special-purpose network device 902, one or more such servers could also be run on a virtualization layer executed by the processor(s) 912); in which case the servers are said to be co-located with the VNEs of that ND.

[00111] A virtual network is a logical abstraction of a physical network (such as that in Figure 9A) that provides network services (e.g., L2 and/or L3 services). A virtual network can be implemented as an overlay network (sometimes referred to as a network virtualization overlay) that provides network services (e.g., layer 2 (L2, data link layer) and/or layer 3 (L3, network layer) services) over an underlay network (e.g., an L3 network, such as an Internet Protocol (IP) network that uses tunnels (e.g., generic routing encapsulation (GRE), layer 2 tunneling protocol (L2TP), IPSec) to create the overlay network).

[00112] A network virtualization edge (NVE) sits at the edge of the underlay network and participates in implementing the network virtualization; the network-facing side of the NVE uses the underlay network to tunnel frames to and from other NVEs; the outward-facing side of the NVE sends and receives data to and from systems outside the network. A virtual network instance (VNI) is a specific instance of a virtual network on a NVE (e.g., a NE/VNE on an ND, a part of a NE/VNE on a ND where that NE/VNE is divided into multiple VNEs through emulation); one or more VNIs can be instantiated on an NVE (e.g., as different VNEs on an ND). A virtual access point (VAP) is a logical connection point on the NVE for connecting external systems to a virtual network; a VAP can be physical or virtual ports identified through logical interface identifiers (e.g., a VLAN ID).

[00113] Examples of network services include: 1) an Ethernet LAN emulation service (an Ethernet-based multipoint service similar to an Internet Engineering Task Force (IETF) Multiprotocol Label Switching (MPLS) or Ethernet VPN (EVPN) service) in which external systems are interconnected across the network by a LAN environment over the underlay network (e.g., an NVE provides separate L2 VNIs (virtual switching instances) for different such virtual networks, and L3 (e.g., IP/MPLS) tunneling encapsulation across the underlay network); and 2) a virtualized IP forwarding service (similar to IETF IP VPN (e.g., Border Gateway Protocol (BGP)/MPLS IP VPN) from a service definition perspective) in which external systems are interconnected across the network by an L3 environment over the underlay network (e.g., an NVE provides separate L3 VNIs (forwarding and routing instances) for different such virtual networks, and L3 (e.g., IP/MPLS) tunneling encapsulation across the underlay network)). Network services may also include quality of service capabilities (e.g., traffic classification marking, traffic conditioning and scheduling), security capabilities (e.g., filters to protect customer premises from network - originated attacks, to avoid malformed route announcements), and management capabilities (e.g., full detection and processing).

[00114] Figure 9D illustrates a network with a single network element on each of the NDs of Figure 9A, and within this straight forward approach contrasts a traditional distributed approach (commonly used by traditional routers) with a centralized approach for maintaining reachability and forwarding information (also called network control), according to some embodiments of the invention. Specifically, Figure 9D illustrates network elements (NEs) 970A-H with the same connectivity as the NDs 900A-H of Figure 9A. [00115] Figure 9D illustrates that the distributed approach 972 distributes responsibility for generating the reachability and forwarding information across the NEs 970A-H; in other words, the process of neighbor discovery and topology discovery is distributed.

[00116] For example, where the special-purpose network device 902 is used, the control communication and configuration module(s) 932A-R of the ND control plane 924 typically include a reachability and forwarding information module to implement one or more routing protocols (e.g., an exterior gateway protocol such as Border Gateway Protocol (BGP), Interior Gateway Protocol(s) (IGP) (e.g., Open Shortest Path First (OSPF), Intermediate System to Intermediate System (IS-IS), Routing Information Protocol (RIP), Label Distribution Protocol (LDP), Resource Reservation Protocol (RSVP) (including RSVP-Traffic Engineering (TE): Extensions to RSVP for LSP Tunnels and Generalized Multi-Protocol Label Switching

(GMPLS) Signaling RSVP-TE)) that communicate with other NEs to exchange routes, and then selects those routes based on one or more routing metrics. Thus, the NEs 970A-F1 (e.g., the processor(s) 912 executing the control communication and configuration module(s) 932 A-R) perform their responsibility for participating in controlling how data (e.g., packets) is to be routed (e.g., the next hop for the data and the outgoing physical NI for that data) by

distributively determining the reachability within the network and calculating their respective forwarding information. Routes and adjacencies are stored in one or more routing structures (e.g., Routing Information Base (RIB), Label Information Base (LIB), one or more adjacency structures) on the ND control plane 924. The ND control plane 924 programs the ND forwarding plane 926 with information (e.g., adjacency and route information) based on the routing structure(s). For example, the ND control plane 924 programs the adjacency and route information into one or more forwarding table(s) 934A-R (e.g., Forwarding Information Base (FIB), Label Forwarding Information Base (LFIB), and one or more adjacency structures) on the ND forwarding plane 926. For layer 2 forwarding, the ND can store one or more bridging tables that are used to forward data based on the layer 2 information in that data. While the above example uses the special-purpose network device 902, the same distributed approach 972 can be implemented on the general-purpose network device 904 and the hybrid network device 906.

[00117] Figure 9D illustrates that a centralized approach 974 (also known as software defined networking (SDN)) that decouples the system that makes decisions about where traffic is sent from the underlying systems that forwards traffic to the selected destination. The illustrated centralized approach 974 has the responsibility for the generation of reachability and forwarding information in a centralized control plane 976 (sometimes referred to as a SDN control module, controller, network controller, OpenFlow controller, SDN controller, control plane node, network virtualization authority, or management control entity), and thus the process of neighbor discovery and topology discovery is centralized. The centralized control plane 976 has a south bound interface 982 with a data plane 980 (sometime referred to the infrastructure layer, network forwarding plane, or forwarding plane (which should not be confused with a ND forwarding plane)) that includes the NEs 970A-H (sometimes referred to as switches, forwarding elements, data plane elements, or nodes). The centralized control plane 976 includes a network controller 978, which includes a centralized reachability and forwarding information module 979 that determines the reachability within the network and distributes the forwarding information to the NEs 970A-H of the data plane 980 over the south bound interface 982 (which may use the OpenFlow protocol). Thus, the network intelligence is centralized in the centralized control plane 976 executing on electronic devices that are typically separate from the NDs. In one embodiment, centralized reachability and forwarding information module 979 includes an encryption coordinator 975, which may coordinate the acquisition of the keying materials necessary to secure the communication between an intermediate network device and an endpoint network device as discussed herein above.

[00118] For example, where the special-purpose network device 902 is used in the data plane 980, each of the control communication and configuration module(s) 932A-R of the ND control plane 924 typically include a control agent that provides the VNE side of the south bound interface 982. In this case, the ND control plane 924 (the processor(s) 912 executing the control communication and configuration module(s) 932A-R) performs its responsibility for participating in controlling how data (e.g., packets) is to be routed (e.g., the next hop for the data and the outgoing physical NI for that data) through the control agent communicating with the centralized control plane 976 to receive the forwarding information (and in some cases, the reachability information) from the centralized reachability and forwarding information module 979 (it should be understood that in some embodiments of the invention, the control communication and configuration module(s) 932A-R, in addition to communicating with the centralized control plane 976, may also play some role in determining reachability and/or calculating forwarding information - albeit less so than in the case of a distributed approach; such embodiments are generally considered to fall under the centralized approach 974, but may also be considered a hybrid approach).

[00119] While the above example uses the special-purpose network device 902, the same centralized approach 974 can be implemented with the general purpose network device 904 (e.g., each of the VNE 960A-R performs its responsibility for controlling how data (e.g., packets) is to be routed (e.g., the next hop for the data and the outgoing physical NI for that data) by communicating with the centralized control plane 976 to receive the forwarding information (and in some cases, the reachability information) from the centralized reachability and forwarding information module 979; it should be understood that in some embodiments of the invention, the VNEs 960A-R, in addition to communicating with the centralized control plane 976, may also play some role in determining reachability and/or calculating forwarding information - albeit less so than in the case of a distributed approach) and the hybrid network device 906. In fact, the use of SDN techniques can enhance the NFV techniques typically used in the general purpose network device 904 or hybrid network device 906 implementations as NFV is able to support SDN by providing an infrastructure upon which the SDN software can be run, and NFV and SDN both aim to make use of commodity server hardware and physical switches.

[00120] Figure 9D also shows that the centralized control plane 976 has a north bound interface 984 to an application layer 986, in which resides application(s) 988. The centralized control plane 976 has the ability to form virtual networks 992 (sometimes referred to as a logical forwarding plane, network services, or overlay networks (with the NEs 970A-H of the data plane 980 being the underlay network)) for the application(s) 988. Thus, the centralized control plane 976 maintains a global view of all NDs and configured NEs/VNEs, and it maps the virtual networks to the underlying NDs efficiently (including maintaining these mappings as the physical network changes either through hardware (ND, link, or ND component) failure, addition, or removal).

[00121] While Figure 9D shows the distributed approach 972 separate from the centralized approach 974, the effort of network control may be distributed differently or the two combined in certain embodiments of the invention. For example: 1) embodiments may generally use the centralized approach (SDN) 974, but have certain functions delegated to the NEs (e.g., the distributed approach may be used to implement one or more of fault monitoring, performance monitoring, protection switching, and primitives for neighbor and/or topology discovery); or 2) embodiments of the invention may perform neighbor discovery and topology discovery via both the centralized control plane and the distributed protocols, and the results compared to raise exceptions where they do not agree. Such embodiments are generally considered to fall under the centralized approach 974 but may also be considered a hybrid approach.

[00122] While Figure 9D illustrates the simple case where each of the NDs 900A-H implements a single NE 970 A-H, it should be understood that the network control approaches described with reference to Figure 9D also work for networks where one or more of the NDs 900A-H implement multiple VNEs (e.g., VNEs 930A-R, VNEs 960A-R, those in the hybrid network device 906). Alternatively, or in addition, the network controller 978 may also emulate the implementation of multiple VNEs in a single ND. Specifically, instead of (or in addition to) implementing multiple VNEs in a single ND, the network controller 978 may present the implementation of a VNE/NE in a single ND as multiple VNEs in the virtual networks 992 (all in the same one of the virtual network(s) 992, each in different ones of the virtual network(s) 992, or some combination). For example, the network controller 978 may cause an ND to implement a single VNE (a NE) in the underlay network, and then logically divide up the resources of that NE within the centralized control plane 976 to present different VNEs in the virtual network(s) 992 (where these different VNEs in the overlay networks are sharing the resources of the single VNE/NE implementation on the ND in the underlay network).

[00123] On the other hand, Figures 9E and 9F respectively illustrate exemplary abstractions of NEs and VNEs that the network controller 978 may present as part of different ones of the virtual networks 992. Figure 9E illustrates the simple case of where each of the NDs 900A-H implements a single NE 970 A-H (see Figure 9D), but the centralized control plane 976 has abstracted multiple of the NEs in different NDs (the NEs 970A-C and G-H) into (to represent) a single NE 9701 in one of the virtual network(s) 992 of Figure 9D, according to some embodiments of the invention. Figure 9E shows that in this virtual network, the NE 9701 is coupled to NE 970D and 970F, which are both still coupled to NE 970E.

[00124] Figure 9F illustrates a case where multiple VNEs (VNE 970A.1 and VNE 970H.1) are implemented on different NDs (ND 900A and ND 900H) and are coupled to each other, and where the centralized control plane 976 has abstracted these multiple VNEs such that they appear as a single VNE 970T within one of the virtual networks 992 of Figure 9D, according to some embodiments of the invention. Thus, the abstraction of a NE or VNE can span multiple NDs.

[00125] While some embodiments of the invention implement the centralized control plane 976 as a single entity (e.g., a single instance of software running on a single electronic device), alternative embodiments may spread the functionality across multiple entities for redundancy and/or scalability purposes (e.g., multiple instances of software running on different electronic devices).

[00126] Similar to the network device implementations, the electronic device(s) running the centralized control plane 976, and thus the network controller 978 including the centralized reachability and forwarding information module 979, may be implemented in a variety of ways (e.g., a special purpose device, a general-purpose (e.g., COTS) device, or hybrid device). These electronic device(s) would similarly include processor(s), a set or one or more physical NIs, and a non-transitory machine-readable storage medium having stored thereon the centralized control plane software.

[00127] Standards such as OpenFlow define the protocols used for the messages, as well as a model for processing the packets. The model for processing packets includes header parsing, packet classification, and making forwarding decisions. Header parsing describes how to interpret a packet based upon a well-known set of protocols. Some protocol fields are used to build a match structure (or key) that will be used in packet classification (e.g., a first key field could be a source media access control (MAC) address, and a second key field could be a destination MAC address).

[00128] Packet classification involves executing a lookup in memory to classify the packet by determining which entry (also referred to as a forwarding table entry or flow entry) in the forwarding tables best matches the packet based upon the match structure, or key, of the forwarding table entries. It is possible that many flows represented in the forwarding table entries can correspond/match to a packet; in this case the system is typically configured to determine one forwarding table entry from the many according to a defined scheme (e.g., selecting a first forwarding table entry that is matched). Forwarding table entries include both a specific set of match criteria (a set of values or wildcards, or an indication of what portions of a packet should be compared to a particular value/values/wildcards, as defined by the matching capabilities - for specific fields in the packet header, or for some other packet content), and a set of one or more actions for the data plane to take on receiving a matching packet. For example, an action may be to push a header onto the packet, for the packet using a particular port, flood the packet, or simply drop the packet. Thus, a forwarding table entry for IPv4/IPv6 packets with a particular transmission control protocol (TCP) destination port could contain an action specifying that these packets should be dropped.

[00129] Making forwarding decisions and performing actions occurs, based upon the forwarding table entry identified during packet classification, by executing the set of actions identified in the matched forwarding table entry on the packet.

[00130] However, when an unknown packet (for example, a“missed packet” or a“match- miss” as used in OpenFIow parlance) arrives at the data plane 980, the packet (or a subset of the packet header and content) is typically forwarded to the centralized control plane 976. The centralized control plane 976 will then program forwarding table entries into the data plane 980 to accommodate packets belonging to the flow of the unknown packet. Once a specific forwarding table entry has been programmed into the data plane 980 by the centralized control plane 976, the next packet with matching credentials will match that forwarding table entry and take the set of actions associated with that matched entry.

[00131] A network interface (NI) may be physical or virtual; and in the context of IP, an interface address is an IP address assigned to a NI, be it a physical NI or virtual NI. A virtual NI may be associated with a physical NI, with another virtual interface, or stand on its own (e.g., a loopback interface, a point-to-point protocol interface). A NI (physical or virtual) may be numbered (a NI with an IP address) or unnumbered (a NI without an IP address). A loopback interface (and its loopback address) is a specific type of virtual NI (and IP address) of a NE/VNE (physical or virtual) often used for management purposes; where such an IP address is referred to as the nodal loopback address. The IP address(es) assigned to the NI(s) of a ND are referred to as IP addresses of that ND; at a more granular level, the IP address(es) assigned to NI(s) assigned to a NE/VNE implemented on a ND can be referred to as IP addresses of that NE/VNE.

[00132] Next hop selection by the routing system for a given destination may resolve to one path (that is, a routing protocol may generate one next hop on a shortest path); but if the routing system determines there are multiple viable next hops (that is, the routing protocol generated forwarding solution offers more than one next hop on a shortest path - multiple equal cost next hops), some additional criteria is used - for instance, in a connectionless network, Equal Cost Multi Path (ECMP) (also known as Equal Cost Multi Pathing, multipath forwarding and IP multipath) may be used (e.g., typical implementations use as the criteria particular header fields to ensure that the packets of a particular packet flow are always forwarded on the same next hop to preserve packet flow ordering). For purposes of multipath forwarding, a packet flow is defined as a set of packets that share an ordering constraint. As an example, the set of packets in a particular TCP transfer sequence need to arrive in order, else the TCP logic will interpret the out of order delivery as congestion and slow the TCP transfer rate down.

[00133] A Layer 3 (L3) Link Aggregation (LAG) link is a link directly connecting two NDs with multiple IP-addressed link paths (each link path is assigned a different IP address), and a load distribution decision across these different link paths is performed at the ND forwarding plane; in which case, a load distribution decision is made between the link paths.

[00134] Some NDs include functionality for authentication, authorization, and accounting (AAA) protocols (e.g., RADIUS (Remote Authentication Dial-In User Service), Diameter, and/or TACACS+ (Terminal Access Controller Access Control System Plus). AAA can be provided through a client/server model, where the AAA client is implemented on a ND and the AAA server can be implemented either locally on the ND or on a remote electronic device coupled with the ND. Authentication is the process of identifying and verifying a subscriber. For instance, a subscriber might be identified by a combination of a username and a password or through a unique key. Authorization determines what a subscriber can do after being authenticated, such as gaining access to certain electronic device information resources (e.g., through the use of access control policies). Accounting is recording user activity. By way of a summary example, end user devices may be coupled (e.g., through an access network) through an edge ND (supporting AAA processing) coupled to core NDs coupled to electronic devices implementing servers of service/content providers. AAA processing is performed to identify for a subscriber the subscriber record stored in the AAA server for that subscriber. A subscriber record includes a set of attributes (e.g., subscriber name, password, authentication information, access control information, rate-limiting information, policing information) used during processing of that subscriber’s traffic.

[00135] Certain NDs (e.g., certain edge NDs) internally represent end user devices (or sometimes customer premise equipment (CPE) such as a residential gateway (e.g., a router, modem)) using subscriber circuits. A subscriber circuit uniquely identifies within the ND a subscriber session and typically exists for the lifetime of the session. Thus, a ND typically allocates a subscriber circuit when the subscriber connects to that ND, and correspondingly de allocates that subscriber circuit when that subscriber disconnects. Each subscriber session represents a distinguishable flow of packets communicated between the ND and an end user device (or sometimes CPE such as a residential gateway or modem) using a protocol, such as the point-to-point protocol over another protocol (PPPoX) (e.g., where X is Ethernet or

Asynchronous Transfer Mode (ATM)), Ethernet, 802. IQ Virtual LAN (VLAN), Internet Protocol, or ATM). A subscriber session can be initiated using a variety of mechanisms (e.g., manual provisioning a dynamic host configuration protocol (DHCP), DHCP/client-less internet protocol service (CLIPS) or Media Access Control (MAC) address tracking). For example, the point-to-point protocol (PPP) is commonly used for digital subscriber line (DSL) services and requires installation of a PPP client that enables the subscriber to enter a username and a password, which in turn may be used to select a subscriber record. When DHCP is used (e.g., for cable modem services), a username typically is not provided; but in such situations other information (e.g., information that includes the MAC address of the hardware in the end user device (or CPE)) is provided. The use of DHCP and CLIPS on the ND captures the MAC addresses and uses these addresses to distinguish subscribers and access their subscriber records.

[00136] A virtual circuit (VC), synonymous with virtual connection and virtual channel, is a connection-oriented communication service that is delivered by means of packet mode communication. Virtual circuit communication resembles circuit switching, since both are connection oriented, meaning that in both cases data is delivered in correct order, and signaling overhead is required during a connection establishment phase. Virtual circuits may exist at different layers. For example, at layer 4, a connection-oriented transport layer datalink protocol such as Transmission Control Protocol (TCP) may rely on a connectionless packet switching network layer protocol such as IP, where different packets may be routed over different paths, and thus be delivered out of order. Where a reliable virtual circuit is established with TCP on top of the underlying unreliable and connectionless IP protocol, the virtual circuit is identified by the source and destination network socket address pair, i.e., the sender and receiver IP address and port number. However, a virtual circuit is possible since TCP includes segment numbering and reordering on the receiver side to prevent out-of-order delivery. Virtual circuits are also possible at Layer 3 (network layer) and Layer 2 (datalink layer); such virtual circuit protocols are based on connection-oriented packet switching, meaning that data is always delivered along the same network path, i.e., through the same NEs/VNEs. In such protocols, the packets are not routed individually and complete addressing information is not provided in the header of each data packet; only a small virtual channel identifier (VCI) is required in each packet; and routing information is transferred to the NEs/VNEs during the connection establishment phase;

switching only involves looking up the virtual channel identifier in a table rather than analyzing a complete address. Examples of network layer and datalink layer virtual circuit protocols, where data always is delivered over the same path: X.25, where the VC is identified by a virtual channel identifier (VCI); Frame relay, where the VC is identified by a VCI; Asynchronous Transfer Mode (ATM), where the circuit is identified by a virtual path identifier (VPI) and virtual channel identifier (VCI) pair; General Packet Radio Service (GPRS); and Multiprotocol label switching (MPLS), which can be used for IP over virtual circuits (Each circuit is identified by a label).

[00137] Certain NDs (e.g., certain edge NDs) use a hierarchy of circuits. The leaf nodes of the hierarchy of circuits are subscriber circuits. The subscriber circuits have parent circuits in the hierarchy that typically represent aggregations of multiple subscriber circuits, and thus the network segments and elements used to provide access network connectivity of those end user devices to the ND. These parent circuits may represent physical or logical aggregations of subscriber circuits (e.g., a virtual local area network (VLAN), a permanent virtual circuit (PVC) (e.g., for Asynchronous Transfer Mode (ATM)), a circuit-group, a channel, a pseudo-wire, a physical NI of the ND, and a link aggregation group). A circuit-group is a virtual construct that allows various sets of circuits to be grouped together for configuration purposes, for example, aggregate rate control. A pseudo-wire is an emulation of a layer 2 point-to-point connection- oriented service. A link aggregation group is a virtual construct that merges multiple physical NIs for purposes of bandwidth aggregation and redundancy. Thus, the parent circuits physically or logically encapsulate the subscriber circuits.

[00138] Each VNE (e.g., a virtual router, a virtual bridge (which may act as a virtual switch instance in a Virtual Private LAN Service (VPLS)) is typically independently administrable. For example, in the case of multiple virtual routers, each of the virtual routers may share system resources but is separate from the other virtual routers regarding its management domain, AAA (authentication, authorization, and accounting) name space, IP address, and routing database(s). Multiple VNEs may be employed in an edge ND to provide direct network access and/or different classes of services for subscribers of service and/or content providers.

[00139] Within certain NDs,“interfaces” that are independent of physical NIs may be configured as part of the VNEs to provide higher-layer protocol and service information (e.g., Layer 3 addressing). The subscriber records in the AAA server identify, in addition to the other subscriber configuration requirements, to which context (e.g., which of the VNEs/NEs) the corresponding subscribers should be bound within the ND. As used herein, a binding forms an association between a physical entity (e.g., physical NI, channel) or a logical entity (e.g., circuit such as a subscriber circuit or logical circuit (a set of one or more subscriber circuits)) and a context’s interface over which network protocols (e.g., routing protocols, bridging protocols) are configured for that context. Subscriber data flows on the physical entity when some higher-layer protocol interface is configured and associated with that physical entity.

Alternative Embodiments

[00140] While embodiments of the invention have been described in relation to Figures 2-8, embodiments of the invention are not limited to the ones described relating to Figures 2-8 and alternative embodiments could be implemented.

[00141] While the invention has been described in terms of several embodiments, those skilled in the art will recognize that the invention is not limited to the embodiments described, can be practiced with modification and alteration within the spirit and scope of the appended claims. The description is thus to be regarded as illustrative instead of limiting.