JP2002094605A - Adaptive demultiplexing method and system - Google Patents

Abstract

(57) [Summary] [Object] The present invention aims to adjust the load balance of parallel channels by dynamically reallocating packets. A method and system for combining multiple parallel communication channels to achieve a single broadband communication channel.
A continuous stream of packets is grouped as a traffic aggregate and assigned to queues associated with a plurality of parallel communication channels. Assigning and reassigning traffic aggregates to the queues is performed dynamically based on a queue load ratio measurement associated with the queue length of each parallel communication channel. The grouping of current and future packets as a traffic aggregate is based on common attributes such as common source and destination IP addresses shared by the packets.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION The present invention generally relates to
The present invention relates to a network communication system and a network communication method.
The present invention relates to a method and system for dynamically balancing queues associated with el communication channels.

[0002]

2. Description of the Related Art A conventional network consists of a plurality of network components or nodes, such as computing devices, for example, personal computers, workstations and other similar devices.

[0003] A limited number of network components and devices on a network that connect relatively small areas are local area networks (Local Area Networks).
rk). A network constructed by connecting LANs to each other is a wide area network (Wide-Area Network).
k). A network that connects WANs to each other and a network that connects to other LANs and WANs also
It is called AN. The largest WAN is the Internet (I
nternet), which is a global network to which millions of computing devices are connected.

In a LAN, a WAN, or the Internet (hereinafter, collectively referred to as a “network”),
Most computing devices operate independently of each other, and most computing devices have access to data or other network components residing on a network.

[0005] Interconnecting these computing devices and other network components in a "network" (LAN, WAN or the Internet) requires twisted-pair, coaxial or fiber optic cables and routers, switches and bridges. The formation of a series of communication links or channels by a network device.

However, each communication channel has a limitation such as a bandwidth limitation.

[0007] Bandwidth is attributed to the amount of data, eg, network traffic that can be transferred over a particular communication channel within a particular time. For example, optical carrier level 1
An optical fiber cable conforming to the (OC-1) Optical Synchronous Network (SONET) standard has a bandwidth of 51.8 Mbps, and an OC-3 optical fiber cable has a bandwidth of 155.52 Mbps.

Heretofore, when it was necessary to increase the bandwidth, a high capacity communication channel was installed instead of a low capacity communication channel. For example, the optical fiber cable OC-1
Is changed to fiber optic cable OC-3 and the bandwidth is 100
Mbs was also widened. However, completely swapping one communication channel for another communication channel
Often it is expensive and time consuming.

In addition, the number of communication channels and the number of network devices are proportional to the number of computing devices and other network components in the “network”. Thus, as networks become larger, for example, as more computing devices and other network components are added, the number of cables and network devices also increases. Thus, the cost of replacing the communication channel increases in proportion to the cost of the cable and network device being increased.

In order to reduce these costs, a plurality of communication channels are used in parallel to effectively use the bandwidth.
Therefore, one wideband communication channel is obtained by aggregating a plurality of narrowband parallel-width communication channels. For example, three optical fiber cables OC-1 are combined to obtain a bandwidth of about 155.55 Mbps, which is 155.55 Mbps.
Equivalent to a single fiber optic cable with a bandwidth of 52Mbps.

Similarly, a portion of a wideband communication channel is obtained by aggregating a specified number of narrowband parallel-width communication channels. By aggregating or combining parallel communication channels, the data stream initially located in one communication channel is segmented or split and segmented along one or more parallel communication channels. It is necessary to simultaneously transfer the data flows. This technique is often referred to as demultiplexing.

[0012]

However, the aggregation of parallel communication channels increases the bandwidth,
When parallel communication channels are aggregated, typically the data stream, especially the data packets, ie the envelope containing the data, needs to be segmented at high speed.
Usually, high-speed segmentation of data packets is performed by adding complex network devices.

These composite network devices are necessary to split or decompose data packets and send them over multiple communication channels simultaneously. Further, the composite network device receiving the decomposed packets must reconstruct the data packets in the proper order and format.

Thus, while these composite network devices are less expensive than completely replacing one communication channel with another, they add complexity to the "network" and increase its cost. In addition, as the "network" changes, for example, as faster computing devices join,
Or, as the usage of the “network” changes,
For example, in a "network" that transfers very large amounts of data in different segments at different times, these composite network devices will not be able to adapt to these changes.

It is an object of the present invention to balance the load of said parallel channels by dynamically reallocating packets.

[0016]

SUMMARY OF THE INVENTION The present invention provides a system and method for assembling parallel communication channels to obtain one or a portion of a high bandwidth communication channel. In one embodiment, a method is provided for assembling a plurality of parallel communication channels for transmitting packets, each communication channel being connected to an associated queue.

A method of assembling a plurality of parallel communication channels is to allocate a packet to each queue for each parallel communication channel, measure an average queue load ratio of each channel, and perform parallel communication at the maximum average queue load ratio. Reassigning packets assigned to the channels to parallel communication channels with a minimum average queue load ratio.

In another embodiment, an adaptive network system is provided that includes a first network, a plurality of parallel communication channels connected to the first network, and a second network. The adaptive network system also includes a network switch connected to the second network and the plurality of communication channels.

The network switch includes a plurality of queues associated with each of the plurality of parallel communication channels. Similarly, the network switch is configured to measure an average queue load ratio of each of the plurality of queues and assign a packet to each of the plurality of queues based on the measured average queue load ratio.

In another embodiment, an adaptive network device for sending packets over a plurality of parallel communication channels is provided. The adaptive network device is connected to a plurality of network interface devices connected to a plurality of communication channels, a memory connected to a plurality of network interfaces for storing a plurality of queues associated with each of the plurality of communication channels, and a memory. Includes processor.

[0021] The processor is configured to measure an average queue load ratio of each of the plurality of communication channels and to assign a packet to each queue based on the measured average queue load ratio.

Many of the attendant features of the present invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings. In the drawings, the same elements are denoted by the same reference numerals.

[0023]

FIG. 1 is a block diagram of a conceptual model of an embodiment of the adaptive network system according to the present invention. This conceptual model includes a plurality of interconnected computing devices. For the sake of illustration, the number and interconnection of computing devices is limited, but it is assumed that many and many types of computing devices are used and connected.

The first network 11a is a set or group of computing devices 19a-1 interconnected via a first network cable 21.
9e. In one embodiment,
The first network 11a represents a wide area network WAN. In another embodiment, the first network 11a is a local area network LAN or an intranet.

Similarly, the second network 11b
Group of computing devices 21a connected through network cables 25a to 25d of
21d and the second network device 27. Just as the first network 11a represents a wide area network, in one embodiment the second network 11b represents a wide area network.

In another embodiment, the second network 11b is a local area network LAN or an intranet. In another embodiment, the first and second networks 11a, 11b are segments or portions of a larger network such as the Internet. Further, the first and second networks 11a, 1
The topology of 1b is illustrated as a Bus topology and a Star topology, respectively. However, in other embodiments, other topologies of the first and second networks 11a, 11b are used.

It is an adaptive network device 17 that connects the first network 11a and the second network 11b. In one embodiment, the adaptive network device 17 is included in the first network 11a. The adaptive network device 17 is connected to the first network via the interconnect cable 13. In one embodiment, interconnect cable 13 is a single broadband fiber optic cable.

In another embodiment, the first network cable 21 is a plurality of communication cables, such as a fiber optic cable or a coaxial cable bundle. The adaptive network device 17 is likewise connected to the second network 11b through a set of parallel communication channels 15. In another embodiment, the adaptive network device 17 is further connected to an additional network through an additional communication channel similar to the set of parallel communication channels 15. In one embodiment, these parallel communication channels are OC-3 level fiber optic cables.

A continuous stream of data packets is passed through the adaptive network device 17 to the first network 11.
a and the second network 11b. In one embodiment, the header of the data packet is inspected by the adaptive network device 17 and the data packet is sent out to the first network 11a or the second network 11b or to another network (not shown). Can be

The header of the data packet contains destination information such as the destination Internet Protocol (IP) address. In one embodiment, a network device (not shown) in the first network 11a or a second network device in the second network 11b filters the data.

Thus, only data from the first network to the second network or vice versa, or
And data sent only through the second network to other networks is sent to the adaptive network device 17.

FIG. 2 is a simplified block diagram of one embodiment of the adaptive network device 17 in FIG.
In FIG. 2, the adaptive network device 17 is a first,
Second and third parallel communication channels 115A-115
Connected to C. The adaptive network device 17 appropriately selects and determines a parallel communication channel for transmitting the received data packet.

In one embodiment, adaptive network device 17 receives a continuous stream of data packets. As data packets arrive or are received, the adaptive network device groups the data packets into a collection of one or more single units or traffic. Therefore, a set of traffic can be regarded as a set of continuous traffic flows, that is, a set of continuous data packets.

[0034] A collection of these traffics is individually assigned to parallel communication channels selected by the adaptive network device. The first, second, and third queues 117A-117C are individually connected to first, second, and third parallel communication channels 115A-115C.
Traffic aggregates assigned to a particular parallel communication channel are temporarily stored in a queue associated with a given communication channel.

If the parallel communication channels can service the aggregate of traffic stored in each queue, the packets of the traffic aggregate held in each queue are transferred from the queue to each parallel communication channel. These traffic aggregates are sent to a network connected to the first, second and third parallel communication channels 115A-115C.

FIG. 3 shows a flowchart of the process of sending a data packet to the appropriate network performed by one embodiment of the adaptive network device. In step 21, the process examines the continuous flow of packets from the network to determine certain common criteria or attributes.

In one embodiment, the predetermined common attribute is a destination address contained in the header of the packet. In another embodiment, the predetermined common attributes are source and destination addresses included in the header of the packet. In step 23, the flows of successive packets (current and future packets) are grouped into one or more traffic aggregates by processing based on the determined predetermined common attributes of the packets.

For example, current and future packets containing a destination IP address of 193.23.33.6 are grouped into a first traffic aggregate, and current and future packets containing a destination IP address of 168.23.4.16 are stored in a second traffic aggregate. Grouped into traffic aggregates.

In step 25, the process assigns each traffic aggregate to a particular communication channel or link. In one embodiment, each traffic aggregate is initially assigned to a particular communication channel in sequence by processing.

For example, the first traffic aggregate is the first traffic aggregate.
And the second traffic aggregate is assigned to the second communication channel. In step 27, the process places the traffic aggregate in a queue for the communication channel assigned to the traffic aggregate.

In step 29, it is determined whether the measurement time interval T has been reached. When the measurement time interval T has come, the processing of step 33 measures each queue for each communication channel so that the measured amount becomes the average queue length of the past measurement time interval T.

Based on the measurements in step 33, in step 35, the average queue measurement length for each parallel communication channel is such that the resources for the communication channels are not being used equally, eg, each communication channel has a similar packet transfer delay. , Determine if it indicates.

In the process of step 35, when it is determined that the average queue measurement length for each parallel communication channel uses the resources for the communication channel equally, the process returns to step 21. Similarly, if it is determined in the processing of step 29 that the measurement time interval T has not been reached,
The process returns to step 21.

However, if it is determined in step 35 that the resources of the communication channel are not equally used based on the average queue measurement length, in step 31 the future traffic aggregate is transferred to another communication channel. Reassigned.

Then, the process returns to step 21. FIG.
The process shown in is terminated by the user (shutdown)
The process is terminated when a predetermined condition or action from the outside such as an instruction, power removal of the adaptive network device, or the like occurs.

FIG. 4 shows a detailed model of one embodiment of the adaptive network device of the present invention. The adaptive network device 17 shown in FIG. 4 is divided into four operating units. These operating units are assigned unit 131,
Mapping unit 133, buffer unit 135,
The balance unit 137 is included. Assignment unit 13
1 receives a continuous stream of packets from a particular network.

The allocation unit 131 further checks the header of the received packet to identify the destination address of the packet to be transmitted. By using the destination address, the assignment unit 131 determines a particular key or number to assign to the current set of packets. This unique key is determined using a hash function in the description of the present embodiment.

This hash function provides a mathematical formula that generates a unique attribute or characteristic, ie, a group of items according to or part of a common destination IP address, ie, a unique number for a data packet. In one embodiment, the function H (p) modulo N is employed, where H (p) is a hash function applied to the packet set p and N is the traffic set defined by the adaptive network device. The total number of bodies.

For example, a packet containing a destination IP address of 127.188.169.70 generates a hash value of 5, and
Packets containing 90 destination IP addresses generate a hash value of 7. Thus, through the use of a hash function, packet groups (current and future) based on the destination IP address will generate a unique key or hash value, and other (current and future) packet groups will generate different hash values.

The assignment unit 131 for calculating a hash value or a unique key provides the calculated key for the mapping unit 133.

The mapping unit 133 creates or updates a look-up table that maps traffic aggregates for communication channels using one or more unique keys. In particular, the look-up table contains entries that define the correspondence between a unique key and a communication channel or link. Table 1 is an example of such a lookup table.

[0052]

[Table 1] The first column in Table 1 represents a key or unique hash value for a particular traffic aggregate. The second column represents the communication channel or link for the unique key. Thus, as shown in Table 1, an aggregate with 11 keys maps to a 3 link, and an aggregate with 7 keys maps to a 1 link.

The mapping unit 133 updates the look-up table at each load adjustment interval or measurement time interval T. The measurement time interval T is a predetermined time such as one second, and the measurement of each queue of each communication channel is performed at this time.

The measurement time interval T is the balance unit 137
Set, monitored, and maintained by The balance unit 137 likewise monitors the buffer unit 135, in particular the queues associated with the parallel communication channels 15A to 15D.

In one embodiment, a single queue is for each parallel communication channel connected to the adaptive network device. In another embodiment, a plurality of queues are for each parallel communication channel connected to the adaptive network device.

In another embodiment, multiple queues are associated with several parallel communication channels, and a single queue is associated with the remaining parallel communication channels. In FIG. 4, queues 139A-139C are associated with parallel communication channels 15A-15C, respectively. Also, first, second, third and fourth queues 201, 203, 205 and 2
07 relates to the communication channel 15D.

The queue scheduler 211 included in the buffer unit 135 determines the service order of the first, second, third and fourth queues 201, 203, 205 and 207. The service order determines the order in which the communication channel searches for packets from the queue. In one embodiment, the queue scheduler sets priorities that define service orders for each queue. The queue with the highest priority is the queue from which the communication channel searches for packets from the beginning. In another embodiment, the queue scheduler sets the service order in order.

For example, the queue scheduler searches for a packet until the queue becomes empty, and thereafter searches for a packet from the next queue or the like. In one embodiment, queue scheduler 211 can set absolute priority for queue 201. Therefore, packets from queue 203 will not be retrieved unless queue 201 is empty. In addition, the queue scheduler differentiates services and guarantees quality by defining service orders and the buffer unit placing critical packets in the highest priority queue, respectively.

In other words, certain packets and their applications are given a higher priority or status in the service order, followed by other packets. Thus, higher priority packets are provided with improved service and quality assurance over other packets having lower service ranks.

As described above, the mapping unit 133 has a queue mapping table.
Table 2 is an example of the queue mapping table.

[0061]

[Table 2] The queue mapping table is related to the queue by a link. The first column of Table 2 contains a unique queue number representing the queue associated with each communication channel or link. The second column contains the unique link number associated with the unique link. For example, queues 5, 6 and 7 are assigned to link 3 and queues 8 and 9 are assigned to link 4.

In one embodiment, using a queue mapping table, the mapping unit 133 and the balance unit 137 perform queue assignment and reallocation. For example, if link 3 becomes overloaded, queues 6 and / or 7 are reassigned to link 4.

Thus, if queue 6 is reallocated due to link 3 overload, the traffic aggregate will be moved from link 3 to link 4 as well. if,
When one single queue is assigned to one link,
In one embodiment, new queues are dynamically created by buffer 133 as needed. For example, queue 1
Is assigned to link 1 and queue 2 is assigned to link 2.

If link 1 is overloaded,
Queue 1 is reassigned to link 2. In addition, it is possible to reassign queue 2 to link 1. Alternatively, a new queue is dynamically created by buffer unit 135 and assigned to link 1. Similarly, the look-up table described in Table 1 can be modified to map traffic aggregates by queue instead of link. Table 3 is an example of a modified lookup table.

[0065]

[Table 3] In one embodiment, the mapping between traffic aggregates and queues is fixed, ie, traffic aggregates cannot be reassigned to other queues by the balance unit 137. Thus, when a link becomes overloaded, one queue and the current packets in the queue are moved to another link.

Thus, when a queue is reassigned or moved, the current packet and potential future packets are moved as well. As a result, forwarding of packets from the same application that is simultaneously transmitted on different links is prevented. Therefore, these packets are not reordered.

Each queue operates as a buffer holding packets belonging to a traffic aggregate sent over the associated communication channel. During the measurement time interval T, these cues of each communication channel are measured by the balance unit 137. In particular, the average queue length of each communication channel is measured. The average queue length during the measurement time interval T is determined using equations 1a-1c. _{Q x ← Q x + q p} * L p in (Equation _{1a) avg (q x) ←} Q x / C x T ( Equation 1b) Q _x ← 0 (formula 1c) Formula 1 a to 1 c, L _p is the packet p , Q _p is the instantaneous queue length when packet p is transmitted, c _x is the measured capacity of the communication channel (maximum number of bits transmitted per second), and Q _x is the temporary queue total Variable. Mathematically, the average queue length avg (q _x ) during the measurement time interval T calculates the sum of the functions of the queue lengths for the communication channels at the measurement time interval T and the measurement at the end of the measurement time interval T Determined by dividing the sum by the time interval T. Equation 1
This mathematical calculation is reflected in a to 1c.

Since the queue length is maintained at a fixed level or the length when the packet is transmitted, the queue length for the communication channel when the packet is sent is the queue length for the last moment (L _p / C _x ). equal to the length q _p. Therefore, the total value is a value obtained by multiplying the size of the transmitted packet L _p by the measured communication channel capacity C _x and multiplying by q _p for all the packets transmitted during the measurement time interval T.
(Ie, calculated as the sum of the instantaneous queue lengths equal to q _p * (L _p / C _x ).

However, in order to avoid troublesome division when each packet is transmitted, division by the communication channel capacity c _x measured at the measurement time interval T is performed at the end of the measurement time interval T.

Therefore, referring to equations 1a to 1c and FIG. 4, at the beginning of the measurement time interval T, the communication channel X
The temporary queue sum variable Q _{x for} is zero. During the measurement time interval T for each packet sent from the communication channel X, the balance unit 137 continuously calculates a temporary queue total variable Q _x (Eq. 1a). In other words, equation 1a is calculated each time a packet is sent.

At the end of the measurement time interval T, a temporary key
Queue total variable Q_xIs the password sent from communication channel X.
Ket L_pThe product of the sizes of q_pDouble the total instantaneous queue length
is there. Similarly, at the end of the measurement time interval T, the communication channel
Average queue length avg (q _x) Indicates the measured communication channel.
Channel c_xAnd divide the measurement time interval T (Equation 1b)
It is calculated by

Once the average queue length has been calculated, the temporary queue total variable Q _x is zeroed in preparation for the next measurement time interval T and the beginning of the next calculation of the temporary queue total variable Q _x ( Formula 1c). Once the average queue length has been measured for each of the queues for the parallel communication channels, balance unit 137 determines a minimum average queue length and a maximum average queue length for each queue.

By dividing the average queue length by the measured communication channel capacity, the average queue load ratio (average q
ueue load ratio). Accordingly, the balance unit 137 provides a minimum average queue load ratio QR to a minimum and maximum average queue length for each parallel communication channel.
Determine _min and maximum average queue load ratio QR _max .

Furthermore, the balance unit 137 determines whether any of the queues and any of the parallel communication channels are overloaded, ie, the measurement of the queue load ratio is based on the fact that the resources for the communication channels or queues are not being used equally. Is determined. In one embodiment, balance unit 137 makes this determination by comparing the minimum average queue load ratio QR _min and the maximum average queue load ratio QR _max, as shown in equation 2.

QR _max > ∝ (QR _min ) (Equation 2) In Equation 2, the maximum average queue load ratio QR _max is q _max / c
equal to _max , the minimum average queue load ratio QR _min is q _min / c
equal to _min . Here, q _max and q _min are the maximum and minimum average queue lengths, respectively, and c _max and c _min are the communication channel capacities for the maximum and minimum average queue lengths, respectively.

The coefficient ∝ is a modifier for a predetermined threshold value indicated by the minimum average queue load ratio QR _min . If the communication channel is determined to be overloaded by the balance unit 137, the balance unit 137 notifies the mapping unit 133 to reallocate the traffic aggregate, ie, to reallocate the oldest traffic aggregate. Notify the mapping unit 133. The oldest traffic aggregate is the last traffic aggregate assigned to the communication channel with the highest average queue load ratio. Similarly, future packets of the oldest traffic aggregate will
It is sent to the communication channel having the minimum queue load ratio, not the communication channel having the queue with the maximum queue load ratio.

The possibility of packets not being sent in order is reduced by the mapping unit 133, which assigns and reassigns traffic aggregates as individual units to communication channels. However, packets may be sent out of order while traffic aggregates are being remapped or reassigned to different communication channels.

By sending packets out of order, the receiving network device requires more processing power to reorder or reassemble the order of the packets for data transmission. By adjusting the coefficient の in Equation 2, the balance unit 137 can be dynamically configured so that packets are not sent out of order as much as possible.

In order to increase the value of the coefficient の in the equation (2),
Since the frequency of satisfying the condition of Equation 2 is reduced, the reallocation of a traffic aggregate in which packets are transmitted out of order is reduced. In other words, the balance unit 13
7 is less often, but the predetermined threshold of the coefficient ∝ (QR _min ) is often the maximum average queue load ratio QR
Since it is larger than _max , it is determined that the queue and the parallel communication channel are overloaded.

The product N * T (N is the number of traffic aggregates,
(T is a measurement time interval), the balance unit 137 can further dynamically minimize out-of-order transmission of packets. The product N * T represents the degree to which a single traffic aggregate other than the N traffic aggregate is reallocated for all measurement time intervals T. Since out-of-order packet transmission occurs during the reassignment of traffic aggregates from one communication channel to another, the larger the product N * T, the less out-of-order packet transmission.

Conversely, the smaller the product N * T, the more often out-of-order transmission of packets will occur. However, the smaller the product N * T, the more often traffic aggregates are reassigned. Thus, the number of traffic aggregates assigned to each communication channel can be better balanced so as to balance the load or length of the queue associated with each communication channel.

Returning to FIG. 3 together with FIG. 4, in one embodiment, the operation unit shown in FIG. 4 is configured to perform the processing shown in FIG. Steps 21 and 23 are performed by the allocation unit 131. Step 2
5 is performed by the mapping unit 133, and step 27 is performed by the buffer unit 135. Steps 29, 31, 33 and 35 are performed by the balance unit 13
7 is performed. Similarly, in another embodiment, the operations performed by the unit shown in FIG.
Are included in the processing shown in FIG.

FIG. 5 shows a block diagram of one embodiment of the adaptive network device of the present invention. In one embodiment, the adaptive network device is a standalone network device or a computing device, such as a personal computer, programmed by firmware or software. Adaptive network devices are network interface devices 81 and 8
Data is transmitted and received via 3A-C.

Network interface device 8
The data received by 1 is sent from various computers connected to other computers connected to the network interface devices 83A to 83C. The continuous stream of data packets is continuously received by the network interface device 81 and transferred via the bus 85.

The processor 87 connected to the bus 85 verifies the transfer data and determines which specific queue holds the data. Related communication channels 91A-
The queue for 91C is stored in memory 89. The queues are of various sizes and configurations. In the above embodiment, the queue is held in memory 89
This is a data structure of FIFO (First In First Out).

The memory 89 also stores a look-up table in which packet groups are assigned to the communication channels 91A to 91C. When the queue in the memory 89 is filled by the processor 87,
The network devices 83A-83C for queues in memory 89 delete data from the appropriate queues.
Network interface devices 83A to 83C
Deletes data from the queue based on the availability of each communication channel 91A-91C.

The communication channels 91A to 91C are parallel narrow bandwidth communication channels such as OC-1 level optical fibers. Therefore, when data is transferred through the network interface device 81, the data is immediately transferred through the parallel communication channels 91A to 91C.

In addition, queues for parallel communication channels are maintained and balanced by the processor. The processor changes the entries, ie remaps the entries in the look-up table, to balance the queues and prevent one queue and one communication channel from being overloaded. The processor also makes measurements and analyzes to keep this balance.

Accordingly, the present invention provides an adaptive network device and method for a network using the adaptive network device. Although the invention has been described with reference to specific embodiments, those skilled in the art will perceive other changes and modifications. Thus, it will be appreciated that the invention can be practiced other than as described above. (Supplementary Note 1) In an adaptive demultiplexing method, a plurality of parallel communication channels for transmitting packets are aggregated, and each parallel communication channel is connected to an associated queue. Packets are stored in the queue for each of the plurality of parallel communication channels. Allocating; calculating an average queue load ratio for each of the plurality of parallel communication channels; and averaging a packet allocated to a first one of the plurality of parallel communication channels by a maximum average queue load ratio. Reallocating to a second of the plurality of parallel communication channels according to a queue load ratio. (Supplementary note 2) The statement in Supplementary note 1, comprising a step of determining a plurality of traffic aggregates and a step of assigning each of the plurality of traffic aggregates to each of the plurality of parallel communication channels based on a predetermined map. A featured adaptive demultiplexing method. (Supplementary note 3) The adaptive demultiplexing method according to supplementary note 2, wherein a predetermined map is determined for each of the plurality of parallel communication channels from a look-up table representing each of the plurality of traffic aggregates. . (Supplementary note 4) The adaptive demultiplexing method according to supplementary note 3, wherein each of the plurality of traffic aggregates is a packet set having at least one predetermined attribute in common. (Supplementary note 5) The adaptive demultiplexing method according to supplementary note 4, wherein at least one predetermined attribute is a common key determined based on a destination of the packet. (Supplementary Note 6) In the supplementary note 5, the common key is a hash value, and the hash value is a unique value calculated using a hash value function based on a destination Internet protocol address of the packet. Adaptive demultiplexing method. (Supplementary Note 7) In the supplementary note 1, the assignment of the packet includes a step of determining a plurality of traffic aggregates and a process of randomly assigning each of the plurality of traffic aggregates to each of the plurality of parallel communication channels. An adaptive demultiplexing method characterized by: (Supplementary note 8) The adaptive demultiplexing method according to supplementary note 7, wherein each of the plurality of traffic aggregates is a packet set having at least one common predetermined attribute. (Supplementary note 9) The adaptive demultiplexing method according to supplementary note 8, wherein the at least one predetermined attribute is a common key determined based on a destination of the packet. (Supplementary Note 10) In the supplementary note 9, the common key is a hash value, and the hash value is a unique value calculated by using a hash value function based on a destination Internet protocol address of the packet. Adaptive demultiplexing method. (Supplementary Note 11) In calculating the average queue load ratio for each of the plurality of communication channels described in Supplementary Note 1, for each of the parallel communication channels, all bytes included in the packet allocated to the queue are averaged queue length. Measuring, determining the capacity of each of the plurality of parallel communication channels, and dividing the measured average queue length by each capacity determined for each of the plurality of parallel communication channels. Adaptive demultiplexing method. (Supplementary Note 12) In the measurement of the average queue length of each communication channel described in Supplementary Note 12, a step of measuring a size of a transfer packet transmitted from the queue, and determining a queue length when the transfer packet is transmitted from the queue. And determining the capacity of one of the plurality of parallel communication channels associated with the queue. (Supplementary Note 13) In the measurement of the average queue length of each of the parallel communication channels according to Supplementary Note 12, transmission packets are output from the queue for all packets output from the queue during a predetermined measurement time interval. Summing the product of the sizes of the transmitted packets determined by the time length of the queue, and dividing the sum by the capacity determined by the plurality of parallel communication channels for the queue and one of the predetermined measurement time intervals. An adaptive demultiplexing method comprising the steps of: (Supplementary note 14) The adaptive demultiplexing method according to supplementary note 12, wherein the predetermined measurement time interval is approximately 0.5 to 1.5 seconds. (Supplementary note 15) The adaptive demultiplexing method according to Supplementary note 1, characterized in that the method further includes continuously reallocating packets at predetermined time intervals. (Supplementary note 16) The adaptive demultiplexing method according to supplementary note 12, wherein the predetermined time interval is one second. (Supplementary Note 17) A first network, a plurality of parallel communication channels connected to the first network, a second network, a network switch connected to the second network and the plurality of communication channels, Including a plurality of queues for each of the parallel communication channels, measuring an average queue load ratio of each of the plurality of queues,
An adaptive network system for allocating or reallocating packets to each of a plurality of queues based on a measured average queue load ratio. (Supplementary note 18) In the adaptive network device according to Supplementary note 17, wherein the network switch assigns or reassigns a packet to each of the plurality of queues and a memory having a plurality of queues, and an average queue of each of the plurality of parallel communication channels. An adaptive network system comprising a processor configured to measure a load ratio. (Supplementary Note 19) In an adaptive network device that transmits a packet through a plurality of communication channels, a plurality of network interface devices connected to a plurality of parallel communication channels, and a plurality of network interface devices connected to the plurality of network interface devices and associated with each of the plurality of communication channels. And a memory connected to the memory for measuring an average queue load ratio of each of a plurality of communication channels, and allocating and reallocating packets to a plurality of queues based on the measured average queue load ratio. An adaptive network device comprising: a processor; (Supplementary note 20) In the supplementary note 19, the processor further determines a capacity of each of the plurality of communication channels, groups the packets into a track aggregate, and sets a traffic aggregation for each of the plurality of communication channels based on the measured average queue load ratio. An adaptive network device configured to assign and reassign packets by assigning a body. (Supplementary note 21) The adaptive network device according to supplementary note 20, wherein each of the traffic aggregates is a set of packets having at least one predetermined attribute in common. (Supplementary note 22) The adaptive network device according to supplementary note 21, wherein the at least one predetermined attribute is a common key determined based on a destination of the packet. (Supplementary note 23) The adaptive network device according to supplementary note 22, wherein the common key is a hash value, and the hash value is a unique number calculated using a hash function based on a destination Internet protocol address of the packet. Adaptable network device. (Supplementary note 24) In the adaptive network device according to Supplementary note 23, the processor measures an average queue length for each of the plurality of communication channels so as to be a total number of bytes of a packet allocated to each of the plurality of queues for each of the plurality of communication channels. Determining the capacity of each of the plurality of communication channels of the associated queue, and measuring the average queue load ratio of each of the plurality of communication channels by dividing the determined average queue length by the determined capacity of each of the plurality of communication channels. An adaptive network device, characterized in that: (Supplementary note 25) In the adaptive network device according to Supplementary note 24, the processor is configured to continuously measure an average queue load ratio of each of the plurality of communication channels for a plurality of predetermined time intervals, and the plurality of the predetermined plurality of communication channels. An adaptive network device for reassigning packets to each queue based on an average queue load ratio measured over a time interval. (Supplementary note 26) The adaptive network device according to supplementary note 25, wherein each of the plurality of time intervals has a length of one second. (Supplementary note 27) In an adaptive network device that transmits a packet through a plurality of parallel communication channels, a plurality of network interface devices connected to the plurality of communication channels, and a plurality of network interface devices connected to the plurality of network interface devices and related to each of the plurality of communication channels. A memory for storing a plurality of queues, an average queue load ratio of each of the plurality of communication channels connected to the memory, and a plurality of queues for each of the plurality of communication channels based on the measured average queue load ratio. A processor for assigning a set of queues. (Supplementary note 28) The adaptive network device of Supplementary note 27, wherein the processor measures an average queue load ratio of each of the plurality of communication channels, groups the packets into a traffic aggregate, and measures the measured average queue load of each of the plurality of communication channels. An adaptive network device configured to assign packets by assigning a traffic aggregate to each of a plurality of communication channels based on a ratio. (Supplementary note 29) The adaptive network device according to supplementary note 28, wherein each of the traffic aggregates is a set of packets having at least one predetermined attribute in common. (Supplementary note 30) The adaptive network device according to supplementary note 29, wherein at least one predetermined attribute is a common key determined based on a destination of the packet. (Supplementary note 31) The adaptive network device according to supplementary note 30, wherein the common key is a hash value, and the hash value is a unique number calculated using a hash function based on a destination Internet protocol address of the packet. Adaptable network device. (Supplementary note 32) The adaptive network device according to supplementary note 31, further comprising a queue scheduler connected to the memory and the plurality of network devices, the queue scheduler determining a service order in which a packet is extracted from a plurality of sets of queues. Adaptable network device. (Supplementary note 33) In the adaptive network device according to Supplementary note 32, the processor continuously measures an average queue load ratio of each of the plurality of communication channels for the plurality of predetermined time intervals, and for each of the plurality of predetermined time intervals. An adaptive network device configured to reassign a set of queues to each of a plurality of communication channels based on the measured average queue load ratio. (Supplementary note 34) The adaptive network device according to supplementary note 33, wherein each of the plurality of predetermined time intervals is at least 0.5 seconds in length.

[0090]

According to the present invention, it is possible to adjust the load balance of the parallel channels by reallocating the packet having the maximum queue load ratio to the channel having the minimum queue load ratio.

Further, the load balance of the parallel channel can be adjusted by allocating or reallocating packets to each of the plurality of queues based on each average queue load ratio.

[Brief description of the drawings]

FIG. 1 is a block diagram of a conceptual model that is one embodiment of an adaptive network system according to the present invention.

FIG. 2 is a simplified block diagram of one embodiment of an adaptive network device according to the present invention.

FIG. 3 is a flowchart of a process for sending a data packet to an appropriate network performed by one embodiment of an adaptive network device.

FIG. 4 is a diagram showing a detailed model of an embodiment of the adaptive network device according to the present invention.

FIG. 5 is a block diagram of one embodiment of an adaptive network device according to the present invention.

[Explanation of symbols]

 17 adaptive network device 11a first network 11b second network 19a-e computer 21a-d computer 27 adaptive network device

──────────────────────────────────────────────────続 き Continued on the front page (51) Int.Cl. ⁷ Identification symbol FI Theme coat ゛ (Reference) H04L 12/56 H04L 11/20 102F (72) Inventor Tomohiko Taniguchi 4-1-1 Kamiodanaka, Nakahara-ku, Kawasaki-shi, Kanagawa Prefecture. No. 1 Fujitsu Limited F term (reference) 5K028 KK03 SS24 5K030 GA13 HA08 HC01 HC14 HD05 HD06 JA01 LC01 LE03 MB15 5K033 AA03 CB08 CC01 DA05 EC03 5K034 EE08 EE11 HH01 HH02 HH21

Claims (4)

[Claims] 1. An adaptive demultiplexing method, wherein a plurality of parallel communication channels for transmitting packets are aggregated, each parallel communication channel being connected to an associated queue, wherein a packet is stored in the queue for each of the plurality of parallel communication channels. Calculating an average queue load ratio for each of the plurality of parallel communication channels; and determining a packet allocated to a first channel of the plurality of parallel communication channels by a maximum average queue load ratio. Reallocating to a second of the plurality of parallel communication channels according to an average queue load ratio. 2. A first network, a plurality of parallel communication channels connected to the first network, a second network, and a network switch connected to the second network and the plurality of communication channels. Measuring the average queue load ratio of each of the plurality of queues, and assigning or reallocating packets to each of the plurality of queues based on the measured average queue load ratio. An adaptive network system characterized by the following. 3. An adaptive network device for transmitting a packet through a plurality of communication channels, wherein the plurality of network interface devices are connected to a plurality of parallel communication channels, and the plurality of network interface devices are connected to the plurality of network interface devices. A memory for storing a plurality of queues, connected to the memory, measuring an average queue load ratio of each of a plurality of communication channels, and allocating a packet to a plurality of queues based on the measured average queue load ratio and reallocating packets; An adaptive network device. 4. An adaptive network device for transmitting a packet through a plurality of parallel communication channels, a plurality of network interface devices connected to the plurality of communication channels, and a plurality of communication channels connected to the plurality of network interface devices. A memory for storing a plurality of queues for each of the plurality of communication channels, wherein the plurality of queues are connected to the memory to measure an average queue load ratio of each of the plurality of communication channels, and to each of the plurality of communication channels based on the measured average queue load ratio. A processor for allocating a set of queues.