WO2002009390A1

WO2002009390A1 - Computer network system and method for information transfer

Info

Publication number: WO2002009390A1
Application number: PCT/US2001/017805
Authority: WO
Inventors: Scott Charles Evans; Stephen Francis Bush; Amit Bhavanishankar Kulkarni
Original assignee: General Electric Company
Priority date: 2000-07-19
Filing date: 2001-06-01
Publication date: 2002-01-31
Also published as: AU2001265313A1

Abstract

In a computer network (400) comprising a plurality of nodes (402, 404, 408, 410) for communicating information by transmitting packets (100) between source nodes (402) and next hot node (402, 404, 406, 408, 310), a method for optimizing network performance is provided. The method comprises the steps of transmitting a first packet to an intermediate node of the network. The first packet (100) comprises at least direct data (120) comprising directly represented data, and code (110) comprising self optimizing code. The method comprises a further step of executing on at least one next hop node the self optimizing code thereby translating the directly represented data into indirectly represented data.

Description

COMPUTER NETWORKSYSTEM AND METHOD FOR INFORMATION TRANSFER

BACKGROUND OF THE INVENTION

This invention relates to packet switched communication networks and, more particularly, to a packet switched network wherein at least a portion of the packets communicated on the network are self optimizing packets.

Communication between computers has become an important aspect of everyday life in both private and business environments. Networks provide a medium for this communication and further for communication between various types of elements, or nodes, connected to the network such as servers, personal computers, workstations, memory storage systems, or any other component capable of receiving or transmitting data to or from the network.

Computer networks therefore comprise a plurality of computers or nodes interconnected by a communications medium. Each network is defined by at least one communications protocol by which the nodes communicate. A network protocol determines, among other things, the structure of message packets passed between the nodes of the network. Typically a network message packet contains a header portion, a trailer portion and a data portion. The header portion includes a source field containing the network address of the source node which transmitted the message and a destination field containing the network address of the destination node to which the message is directed. The trailer portion includes an error checking field such as a cyclic redundancy check (CRC), while the data portion contains the data to be transmitted between the nodes. In conventional networks the header, data and trailer portions are static, that is, their contents do not change as they are forwarded throughout the network. It is generally desirable to optimize network performance in processing the static packets as they travel through the network. Therefore, computer network resources such as bandwidth, processing power and information storage capabilities are frequently adapted to meet the demands of increasing, or fluctuating loads, i.e., packet traffic. Making networks perform under the most intense loading conditions can be extremely costly, involving capital expenditures in network servers and other hardware, personnel expense in network reconfiguration and lost business due to network down time. Since business conducted over networks such as the Internet, creates wide fluctuations in network loading, a solution to the problem of network optimization that is independent of hardware allocation is needed.

It is further desirable to assure the reliable, accurate and secure transmission of packets. The assurance that information is communicated reliably and accurately as intended by the transmitter, and with proper access as determined by the policies established by the system administrator is critical both to national defense and to the on-going welfare of our electronic commerce based society. Therefore, systems and methods for increasing data security are needed.

BRIEF SUMMARY OF THE INVENTION

In a computer network comprising a plurality of nodes for communicating information by transmitting respective packets from source nodes to next hop nodes, a method for optimizing network performance is provided. The method includes the step of transmitting a self optimizing packet to a next hop node of the network. The self optimizing packet comprises direct data, and self optimizing code. Execution of the optimizing code causes the size of the packets to be adjusted according to characteristics of the corresponding destination nodes. In one embodiment of the invention, the size of the packets are adjusted in accordance with security characteristics of the corresponding destination node. BRIEF DESCRIPTION OF THE DRAWINGS

Figure 1 is a diagram of a self optimizing packet according to an embodiment of the invention.

Figure 2 is a flowchart of the steps carried out by an intermediate node of the present invention in processing an the packet illustrated in FIG. 1.

Figure 3 is a flowchart of the steps of an optimizing algorithm according to an embodiment of the invention.

Figure 4 is pictorial diagram illustrating a network according to an embodiment of the invention.

DETAILED DESCRIPTION OF THE INVENTION

For purposes of this specification the following definitions are provided. A "network" is defined to be two or more processors connected for the purpose of exchanging messages and sharing data and system resources. In one embodiment of the invention a network comprises a local area network (LAN). In another embodiment of the invention, a network comprises a wide area network (WAN), for example, the Internet. The Internet is WAN that connects a plurality (for example thousands) of networks in a plurality of countries, for example, the U.S., Canada, Europe, and Asia. Generally, the Internet provides global communications between computers on networks selected from, but not limited to, the group consisting of government, educational, and industrial networks. In an alternative embodiment of the invention a network comprises a hybrid of LANs and WANs.

A "node" is any device capable of sending, receiving, or sending and receiving information within a network. Nodes are selected from, but not limited to, the group consisting of computers, customized processors, personal computers, main frame computers, minicomputers, lap top computers , routers, switches, repeaters, hubs and the like. More specifically, a "nodes" is an Open Systems Interconnect (OSI) layer 3 device used to extend or inter connect networks. Conventional intermediate nodes forward packets without operating on them. The term "source node" and "destination node" refer to end nodes. End nodes contain the full protocol stack for implemented network protocols.

For purposes of this specification, the term "configured" means including suitable components comprising software components and hardware components, the components being programmed, workably assembled, and integrated to perform the functions described herein.

"Messages" are computer data signals for conveying information over a network. In one embodiment of the invention a "packet switching" architecture is employed to relay messages. The term "packet-switched" describes the type of network in which messages comprise relatively small units of data called packets, and are routed through a network based on the destination address contained within each packet. Breaking communication down into packets allows the same data path to be shared among many users in the network. Packets typically comprise at least a field containing routing information and a field containing the data representing at least a portion of a message. Packets are routed between source and destination nodes in accordance with a predetermined communication protocol. Examples of common communications protocols include Transmission Control Protocol/Internet Protocol (TCP/IP) and Open Systems Interconnection (OSI) protocol.

"Active networks" are computer networks in which computer data signals, i.e., packets, for relaying messages comprise "active packets". An active network comprises a set of active nodes interconnected by various conventional packet forwarding technologies. Each active node comprises an operating system (OS) and one or more execution environments. The OS allocates and schedules the node's resources, e.g., link bandwidth, CPU cycles, and storage. Each execution environment provides a virtual machine which is user programmable. A user programs the node by sending active packets to it. Thus, an EE acts as a shell program much like those found on a general purpose computing system. The EE provides an interface through which end to end network services are accessed. EEs send and receive packets over communication channels. The OS implements these channels using a variety of technologies including, for example, Ethernet and Asynchronous Transfer Mode (ATM), as well as higher level protocols such as TCT, UDP and IP.

For purposes of this specification, "active packets" are data packets that include both data and encoded computer programs. The program code, when executed on a processor, causes the processor to carry out the encoded instructions. In one embodiment of the invention the executable code portion of an active packet is general purpose code, implemented in the JAVA programming language.

The term "active packet forming" refers to methods of the invention whereby the size of an active packet is changed without changing the information content of the packet. Size is measured in total number of bits in the packet including data bits and program bits. The objective of the change is to optimize the packet for execution at its destination node. For purposes of this specification, the term "optimize" means to reduce the total number of bits comprising the packet to the smallest number of bits that can be delivered to the destination node with the information content preserved. In an alternative embodiment of the invention, security and quality of service (QOS) criteria associated with the destination node are considered in optimizing packets.

In one embodiment of the invention, the code portion of the active packet comprises "optimizing code". Optimizing code is a program that optimizes the packet before the packet is forwarded to its destination. To "optimize" means to change the representation of data from direct to indirect, or vice versa. Upon arrival at an intermediate node, e.g., a router, the optimizing code is executed by the router's processor. FIG. 1 illustrates an active packet 100 according to an embodiment of the invention. Active packet 100 comprises data field 110 and optimizing code field 120. In addition to data filed 100 and code field 120, typical packets will contain additional fields including routing information and the like. For purposes of simplification, these additional fields are not shown in FIG. 1. As those of ordinary skill in the art will recognize, fields are a convenient representation for grouping data types within a packet. However, it is to be understood that other techniques exist by which data and code are interspersed within a packet. These remain within the scope of the invention. FIG. 2 is a flow chart illustrating the algorithm 200 executed by an intermediate node, in one embodiment a router, of the invention upon receiving an active packet 100. As shown in step 210 the packet is received. Next as shown in step 300 the optimization code field of the packet is executed by the router, resulting in execution of the optimization algorithm carried by packet 100. As a result, an optimized packet is formed. Finally the optimized packet is forwarded to its destination node as illustrated in step 240.

FIG. 3 illustrates in more detail the steps of an optimizing algorithm implemented by optimizing code segment 120 according to an embodiment of the invention. The first step 303 examine data field 120 of packet 100 to determine its size, that is the total number of bits contained in data field 110. Next, the data is translated into a Finite State Machine (FSM) representation as illustrated in step 305.

In one embodiment of the invention, the entire data stream in field 110 is translated to an FSM representation. In an alternative embodiment of the invention an arbitrary, finite length portion of the data is converted and the remaining portion is left unchanged. Finite State Machines, as they relate to data representations, are known in the art and need not be elaborated upon herein. As those of ordinary skill in the art will recognize, there exist several alternative techniques for translating direct data to indirect data and vice versa.

In many cases, an FSM representation of a given data can be further reduced by employing optimizing techniques once the FSM representation has been obtained. Therefore, in one embodiment of the invention, an FSM optimizer is employed to reduce the size of FSM representation as illustrated in step 307. Such optimizers and techniques are described in the text "Introduction to the Theory of Automata", by Zamir Bavel, ZB Publication Industries, 1989. ISBN number 09623885. Once the optimized FSM representation is obtained, the size, in terms of total bits, of the optimized FSM representation of the data is determined as illustrated in step 311. Next the size of the optimized FSM representation is compared to the size of the original data representation. If the optimized FSM representation is smaller, packet 100 is optimized by forming a new packet wherein data field 110 is replaced by optimized FSM representation 310 as illustrated in step 315. If the optimized FSM representation is larger, packet 100 is unchanged and forwarded to its destination node as illustrated in step 313.

In one embodiment of the invention, data field 110 of packet 100 is examined before the FSM conversion is carried out to determine the complexity of the conversion and to estimate whether the ultimate size of the FSM representation will be smaller than the data representation. Conventional computational complexity theory is employed to make such complexity determinations. As those of ordinary skill in the art will recall, complexity theory is concerned with the classification of problems according to the computational resources required for their solution. Emphasis is placed on the general properties of feasible computations, rather than on algorithms for specific problems.

Accordingly, pre estimating computation complexity saves processing overhead in the router. The optimizing algorithm need not be executed if the results are not likely to optimize packet 100, or if the processing overhead is excessive. In one embodiment of the invention, a conventional Kolmogorov complexity algorithm is employed to make such a pre estimation. If the complexity of the conversion is prohibitive, or if the resulting FSM representation is likely to be larger than the original data representation, the data portion 110 of packet 100 is not changed. That is, packet 100 is forwarded to its destination node with data portion 110 unchanged.

In an alternative embodiment of the invention the optimizing code resides not in self optimizing packet 100, but instead resides in at least one intermediate node of the network. In that embodiment the optimizing code residing in the intermediate node is executed for each packet to be optimized upon the packet's arrival at the intermediate node.

Figure 4 illustrates an example network 400 according to an embodiment of the invention. Network 400 comprises plurality of representative nodes, e.g., 402, 404, 406, 408 and 410. The nodes are coupled together via communication channels 401, 403, 405 and 407. In one embodiment of the invention, the communication channels comprise broadband channels such as provided by conventional fiber connections. In an alternative embodiment of the invention, communication channels 171, 172, 173 and 174 comprise conventional wireless channels. In alternative embodiments of the invention, system 400 comprises both wireless and fiber channels.

A source node 402 generates and transmits active packets 100 and 101 using a conventional routing protocol such as IP (Internet Protocol) routing. IP routing specifies that packets travel through networks one hop at a time (next hop routing) based on the destination address in the IP header of the packet. The entire route is not known at the outset of the journey. Instead, at each stop, the next destination (or next hop) is calculated by matching the destination address of packets 100 and 101 to destination nodes, in this case 406 and 408 respectively. Accordingly, both intermediate nodes 404 and 406 and destination nodes 406 and 408 are at various times, "next hop" nodes for packets 100 and 101.

Active packets 100 and 101 are self optimizing packets in that code fields 110 and 111 respectively, implement the optimizing algorithm illustrated in FIG. 3. In the example shown, packet 100 is routed via intermediate node 404 and likewise, packet 101 is routed through intermediate node 406. It is important to note that for purposes of illustration the characteristics of example destination node 406 and channel 401 as illustrated in FIG. 4 differ from the characteristics of example destination node 408. Specifically, node 406 represents a node having relatively low processing capability. Node 406 is coupled to node 404 by a channel 401 having relatively low bandwidth capability. Node 408 represents a node having relatively high processing capability and channel 402 represents a channel having high bandwidth capability.

The term "node characteristics" as used herein refers to properties of a node which tend to characterize its performance, e.g., processing capacity (CPU capacity), node traffic load, bandwidth capacity, user definable preferences and quality of service (QOS) parameters. CPU capacity refers to the processing power of a node. Node traffic relates to the volume of packets being processed by a node. Bandwidth capacity refers to the processing speed of a node.

In an embodiment of the invention, intermediate nodes 404 and 410 are routers. Routers are devices connecting two or more nodes. Routers operate at the network layer level, instead of the data link layer level. Addressing at the network layer level makes use of an address field for each node, and the address field includes a unique network identifier and a node identifier within the network. Routers make use of the destination node identifier in a message to determine an optimum path from the source node to the destination node. Various routing algorithms are used by routers to determine the optimum paths. Routers include layer 3 functionality for forwarding packets to an appropriate destination node and include functions for performing route calculation, packet fragmentation, and congestion control. Routers have knowledge of the best path that exists between sources and destinations based on information exchanged with other routers that allow the routers to have knowledge of the topology of the network. Factors contributing to the "best" path include cost, speed, traffic, and bandwidth, as well as others. A conventional router's knowledge of network topology in conjunction with an optimal routing algorithm is used to generate routing tables for directing flows of packet traffic according to given Quality of Service (QOS) criteria.

QOS refers to Parameters such as bandwidth, latency, jitter, and error rate and the like. Many conventional networks provide users or applications with a mechanism to indicate their desired quality of service. For example, under the Internet Protocol, datagrams contain three bits, denominated D, T, and R, which if set request low delay (latency), high throughput, and high reliability (i.e. low error rate) respectively (see "Internetworking with TCP/IP; Principles, Protocols, and Architecture" by D Comer, Prentice Hall, 1988, section 7.7.4). The Internet does not guarantee to satisfy these requests, but may be influenced by them in its route selection.

Conventional software running on routers 404 and 410 parses incoming packets 100 and 111 respectively to determine various characteristics about the packets, including the type of the protocol being used and the source and destination(s). Other determinations based on examining the packet may be necessary, such as priority and quality of service (QOS) factors such as priority and bandwidth reservation. Routers 404 and 410 then use the extracted information and compute the next destination for the packets based on topology and route information that is stored in the memory of the routers. The routers also apply QOS rules and actions.

Unlike conventional routers, routers 404 and 410 also execute code portions 110 and 111 respectively of self optimizing packets 100 and 101 respectively. The self optimizing process relies on the fact that data can be represented in one of two ways, direct and indirect. For direct data representation, binary digits symbolize the data itself, e.g., the binary digits 111 symbolize the decimal number 7. Alternatively, in many cases the data can be represented indirectly by means of an algorithm that produces the data as a result of its execution. For example, the constant π can be transmitted in the data portion 106 of packet 105 by including a sufficient number of binary digits to directly represent the value of π to a desired number of decimal places. However, if it is desired to represent, for example, a thousand decimal places, the number of binary digits in data portion 106 of packet

105 will be relatively large. As an alternative, the value of π can be transmitted indirectly in the code portion 107 of a packet by providing the code that implements an algorithm by which π is determined, e.g., divide circumference by diameter. In that case, the binary digits represent instructions to be executed as opposed to an actual number. The choice of whether to represent the data field of a self optimizing packet as a direct data representation or an indirect representation is made by considering the characteristics of the destination node of the packet. For example destination node 406 of FIG. 4 has limited processing resources. In that case it is preferable to minimize the code portion of self optimizing packet 100.

On the other hand, the processing resources of node 408 are not as limited as those of node 406. In that case it is preferable to translate the data field 121 of packet 101 from a direct representation to an indirect representation.

While only certain preferred features of the invention have been illustrated and described, many modifications and changes will occur to those skilled in the art. It is, therefore, to be understood that the appended claims are intended to cover all such modifications and changes as fall within the true spirit of the invention.

Claims

WHAT IS CLAIMED IS:

1. In a computer network (400) comprising a plurality of nodes (402, 404, 406, 408, 410) for communicating information by transmitting packets (100) between source nodes (402) and next hop nodes (404, 406, 408, 410), a method for optimizing network performance comprising the steps of:

transmitting a packet to a next hop node of said network, said packet (400) comprising direct data, and self optimizing code (110);

executing on at least one of said next hop nodes said self optimizing code (110) to provide an optimized packet.

2. The method of claim 1 wherein the step of executing said self optimizing code on said next hop nodes includes the step of translating at least a portion of said direct data to indirect data.

3. The method of claim 1 further including the step of transmitting said optimized packet to a next hop node.

4. The method of claim 1 wherein said next hop node is a router.

5. A computer data signal (100) comprising:

direct data (120) to be conveyed to a next hop node (404, 406, 408, 410);

self optimizing code (110) encoding instructions for optimizing said computer data signal (100).