Routing method based on packet delay
Provided is a routing method for determining a destination in a computer network having multiple interconnected nodes, the method for measuring packet delays among remotely located gateways and processing routing in application layers of the gateways using the packet delays. The routing method based on packet delay includes the steps of setting a re-routing interval and measuring one-way delays among gateways, exchanging the measured delays among the respective gateways and forming delay time tables, calculating an average one-way delay during the re-routing interval, and if a packet is received, applying the calculated average one-way delay to a predetermined algorithm and determining a path from a source gateway to a destination gateway, the path having the minimum delay. Therefore, an improved routing performance can be achieved in real time transmitting a packet by determining the minimum delay path to a destination by measuring packet delays among remotely located nodes in application layers thereof.
1. A method for determining a routing path comprising the steps of:
setting a re-routing interval and measuring one-way delays among gateways;
exchanging the measured delays among the respective gateways and forming delay time tables;
calculating an average one-way delay during the re-routing interval; and
if a packet is received, applying the calculated average one-way delay to a Dijkstra minimum delay algorithm and determining a path from a source gateway to a destination gateway, the path having the minimum delay, wherein the calculation one-way average delay includes calculating one-way average delay in a next re-routing time from a packet delay time (DT) in the current re-routing time with estimation using exponential smoothing average (EXMA), and the step of determining the path having the minimum delay is processed in application layers of gateways.
2. The routing method according to claim 1 , wherein the gateways are VoIP gateways for providing Internet phone service.
3. The routing method according to claim 1 , wherein in the step of determining the path, if the number of accumulated wrong path determinations is greater than or equal to a threshold value, the path is corrected during a next re-routed interval.
4. The routing method according to claim 3 , wherein the case of the routing path is wrongly determined is that Γ l (s,d) is discriminated as 1 according to the following formula 7,
Γ
′
(
s
,
d
)
=
{
1
for
d
avg
l
(
s
,
d
)
-
(
d
avg
l
(
s
,
Ψ
l
(
s
,
d
)
)
+
d
avg
l
(
Ψ
l
(
s
,
d
)
,
d
)
)
<
0
0
for
d
avg
l
(
s
,
d
)
-
(
d
avg
l
(
s
,
Ψ
l
(
s
,
d
)
)
+
d
avg
l
(
Ψ
l
(
s
,
d
)
,
d
)
)
>=
0
[
formulal
7
]
and, the correcting path in the next re-routing interval is performed by the following CTD algorithm
[CTD ALGORITHM]
if Γ l (s,d)=1 then
{
f=f+1
if f<2 then φ l+1 (s,d)=ψ l+1 (s,d)
else φ l+1 (s,d)=d
}
else if Γ l (s,d)=0 then
{
φ l+1 (s,d)=ψ l+1 (s,d)
f=0
}.
5. The routing method according to claim 1 , wherein calculation of one-way average delay with estimation using exponential smoothing average (EXMA) includes using the following formula 5:
{circumflex over (d)} avg l+1 ( i,j )= {circumflex over (d)} lτ ( i,j ) where {circumflex over (d)} lτ ( i,j )=(1−α) d lτ ( i,j )+α {circumflex over (d)} lτ−1 ( i,j ) [formula 5]
where, τ is a re-routing interval, α is EXMA, l is the present re-routing order, and l+1 is the next re-routing order.
6. A method for determining a routing path comprising the steps of:
setting a re-routing interval and measuring one-way delays among gateways;
exchanging the measured delays among the respective gateways and forming delay time tables;
calculating a maximum one-way delay during the re-routing interval; and
if a packet is received, applying the calculated maximum one-way delay to a Dijkstra algorithm and determining a path from a source gateway to a destination gateway, the path having the minimum delay, wherein the calculation of maximum one-way delay includes calculating maximum one-way average delay in a next re-routing time from a packet delay time (DT) in the current re-routing time with estimation using exponential smoothing average (EXMA), and the step of determining the path having the minimum delay is processed in application layers of gateways.
7. The routing method according to claim 6 , wherein the gateways are VoIP gateways for providing Internet phone service.
8. The routing method according to claim 6 , wherein in the step of determining the path, if the number of accumulated wrong path determinations is greater than or equal to a threshold value, the path is corrected during a next re-routed interval.
9. The routing method according to claim 6 , wherein calculation of maximum average delay with estimation using exponential smoothing average (EXMA) includes using the following formula 5:
{circumflex over (d)} avg l+1 ( i,j )= {circumflex over (d)} lτ ( i,j ) where {circumflex over (d)} lτ ( i,j )=(1−α) d lτ ( i,j )+α {circumflex over (d)} lτ−1 ( i,j ) [formula 5]
where, τ is a re-routing interval, α is EXMA, l is the present re-routing order, and l+1 is the next re-routing order.