CALCULATING PACKET DELAY IN A MULTIHOP ETHERNET NETWORK

• US 20110167147A1
• Filed: 04/09/2009
• Published: 07/07/2011
• Est. Priority Date: 04/10/2008
• Status: Abandoned Application

• Current Assignee: Time-Critical Networks AB
• Original Assignee: Time-Critical Networks AB
• Inventors: Lext, Jonas, Andersson, Björn
• Application Number:
  US12/936,182
• Publication Number:
  US 20110167147A1
• Time in Patent Office: Days
• US Class Current: 709/224
• CPC Class Codes: H04L 43/0858 One way delays
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/30 Routing of multiclass traffic
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS
• CPC Class Codes: H04L 45/3065 for real time traffic
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation

Abstract

A method, system, and computer-readable medium for determining the upper bound of the end-to-end delay of a multiframe flow in a multihop Ethernet network. Flows are characterized by the generalized multiframe model, the route of each flow is pre-specified and the output queue of each link schedules Ethernet frames by static-priority scheduling.

Claims

1-66. -66. (canceled)

67. A method for calculating the end-to-end delay of a multiframe real-time flow along a route in a multihop network, the method comprising:

selecting the route in the multihop network, wherein the multiframe real-time flow is capable of being transmitted along the route, the route comprising a source node in the multihop network, a destination node in the multihop network, and at least one intermediate node in the multihop network, the source node comprising either an IP-endhost or an IP-router, the destination node comprising either an IP endhost or an IP-router, and the multiframe real-time flow comprising one or more frames; and

determining an upper bound of a time required to transmit the multiframe real-time flow from the source node to the destination node along the route.

68. The method of claim 67, further comprising determining whether it is possible to offer a delay guarantee for transmission the multiframe real-time flow, wherein the delay conforms to a specified deadline for arrival of the multiframe real-time flow at the destination node, given the upper bound of the time required to transmit the multiframe real-time flow from the source node to the destination node along the route.

69. The method of claim 68, further comprising if it is possible to offer the delay guarantee for transmission of the multiframe real-time flow along the route, transmitting the multiframe real-time flow along the route.

70. The method of claim 68, further comprising if it is possible to offer the delay guarantee for transmission of the multiframe real-time flow along the route, allowing transmission of the multiframe real-time flow.

71. The method of claim 68, further comprising if it is not possible to offer the delay guarantee for transmission of the multiframe real-time flow along the route, denying transmission of the multiframe real-time flow.

72. The method of claim 68, further comprising scheduling transmission of the multiframe real-time flow at a particular time, wherein the particular time at which transmission of the multiframe real-time flow is scheduled is based, at least in part, upon a determination of whether it is possible to offer the delay guarantee for transmission of the multiframe real-time flow along the route.

73. The method of claim 68, further comprising queuing transmission of the multiframe real-time flow, wherein queuing is performed in a manner based, at least in part, upon a determination of whether it is possible to offer the delay guarantee for transmission of the multiframe real-time flow along the route.

74. The method of claim 73, wherein queuing transmission of the multiframe real-time flow is performed in a manner based, at least in part, upon a priority of the multiframe real-time flow.

75. The method of claim 68, further comprising:

if it is not possible to offer the delay guarantee for the multiframe real-time flow, determining whether there is a second route in the multihop network along which the multiframe real-time flow could be transmitted from the source node to the destination node; and

if a second route exists, determining an upper bound of a time required to transmit the multiframe real-time flow from the source node to the destination node along the second route, wherein the upper bound includes delay attributable to generalized jitter.

76. The method of claim 68, further comprising transmitting a message, based upon a determination of whether it is possible to offer the delay guarantee for transmission of the multiframe real-time flow along the route.

77. The method of claim 67, wherein determining the upper bound of the time required to transmit the multiframe real-time flow comprises:

determining a response time required to transmit the frame of the multi frame real-time flow across a first hop of the route, wherein the first hop comprises a link from the source node to a successive node, wherein the determining comprises calculating the response time according to

R_i<sup>k,link(S,succ(τ

i,S))</sup>=(max<sub>q=0 . . . Qik−

1</sub>R_i<sup>k,link(S,succ(τ

i,S))</sup>(q))+prop(S,succ(τ

_i,S))

where Q_i^k is defined as;

78. The method of claim 77, wherein determining the response time comprises determining transmission times for all the Ethernet frames comprising the frame of the multiframe real-time flow, according to a speed of a link for transmitting an Ethernet frame.

79. The method of claim 77, wherein determining the response time comprises determining generalized jitter for each of the Ethernet frames comprising the frame of the multiframe real-time flow as each Ethernet frame is transmitted across the first hop.

80. The method of claim 67, wherein determining the upper bound of the time required to transmit the multiframe real-time flow further comprises determining a response time required to transmit a frame of the multi frame real-time flow across a non-first hop of the route.

81. The method of claim 80, wherein determining the response time required to transmit a frame of the multiframe real-time flow across a non-first hop comprises:

determining a first response time, wherein the determining comprises calculating the first response time according to

R_i^k,in(N)=(max<sub>q=0 . . . Qik−

1</sub>R_i^k,in(N)(q))

and wherein the first response time is measured from a moment when all Ethernet frames comprising a frame of the multiframe real-time flow have been received at a first node until a moment when all the Ethernet frames have been enqueued in a correct priority queue in the first node; and

determining a second response time, wherein the determining comprises calculating the second response time according to

R_i<sup>k,link(N,succ(τ

i,N)</sup>=(max<sub>q=0 . . . Qik−

1</sub>R_i<sup>k,link(N,succ(τ

i,N))</sup>(q))+prop(S,succ(τ

_i,N))

and wherein the second response time is measured from a moment when all Ethernet frames comprising the frame of the multiframe real-time flow have been enqueued in the correct priority queue in the first node until a moment when all the Ethernet frames have been received at a successive node.

82. The method of claim 81, wherein determining the first response time comprises determining generalized jitter for each of the Ethernet frames.

83. The method of claim 81, wherein determining the second response time comprises determining transmission times for all the Ethernet frames, according to a speed of a link for transmitting an Ethernet frame;

and determining generalized jitter for each of the Ethernet frames.

84. A method for analyzing schedulability of a multiframe real-time flow in a multihop network, the method comprising:

selecting a route in the multihop network, wherein the multiframe real-time flow is capable of being transmitted along the route, the route comprising a source node in the multihop network, a destination node in the multihop network, and at least one intermediate node in the multihop network, the source node comprising either an IP-endhost or an IP-router, the destination node comprising either an IP-endhost or an IP-router, and the multiframe flow comprising one or more frames;

looking up an end-to-end delay of the multiframe real-time flow along the route in the multihop network; and

determining whether it is possible to offer a delay guarantee for the multiframe real-time flow, wherein the delay conforms to a specified deadline for arrival of the multiframe real-time flow at the destination node, given an upper bound of a time required to transmit the multiframe real-time flow from the source node to the destination node along the route.

85. The method of claim 84, wherein looking up the end-to-end delay of the multiframe real-time flow along the route in the multihop network comprises accessing another node in the network, wherein the end-to-end delay of the multiframe real-time flow along the route in the multihop network is stored on the other node.

86. The method of claim 84, wherein looking up the end-to-end delay of the multi frame real-time flow along the route in the multihop network comprises accessing a database, wherein the end-to-end delay of the multiframe real-time flow along the route in the multihop network is stored in the database.

87. The method of claim 84, wherein looking up the end-to-end delay of the multiframe real-time flow along the route in the multihop network comprises accessing an in-memory lookup table, wherein the end-to-end delay of the multiframe real-time flow along the route in the multihop network is stored in the in-memory lookup table.

88. The method of claim 84, further comprising if it is possible to offer the delay guarantee for transmission of the multiframe real-time flow along the route, transmitting the multiframe real-time flow along the route.

89. The method of claim 84, further comprising if it is possible to offer the delay guarantee for transmission of the multi frame real-time flow along the route, allowing transmission of the multiframe real-time flow.

90. The method of claim 84, further comprising if it is not possible to offer the delay guarantee for transmission of the multiframe real-time flow along the route, denying transmission of the multiframe real-time flow.

91. The method of claim 84 further comprising scheduling transmission of the multiframe real-time flow at a particular time, wherein the particular time at which transmission of the multiframe real-time flow is scheduled is based, at least in part, upon a determination of whether it is possible to offer the delay guarantee for transmission of the multiframe real-time flow along the route.

92. The method of claim 84, further comprising queuing transmission of the multiframe real-time flow, wherein queuing is performed in a manner based, at least in part, upon a determination of whether it is possible to offer the delay guarantee for transmission of the multiframe real-time flow along the route.

93. The method of claim 92, wherein queuing transmission of the multiframe real-time flow is performed in a manner based, at least in part, upon a priority of the multiframe real-time flow.

94. The method of claim 84, further comprising:

if it is not possible to offer the delay guarantee for the multiframe real-time flow, determining whether there is a second route in the multihop network along which the multiframe real-time flow could be transmitted from the source node to the destination node; and

if a second route exists, determining an upper bound of a time required to transmit the multiframe real-time flow from the source node to the destination node along the second route, wherein the upper bound includes delay attributable to generalized jitter.

95. The method of claim 84, further comprising transmitting a message, based upon a determination of whether it is possible to offer the delay guarantee for transmission of the multiframe real-time flow along the route.

96. A computer-readable medium, on which is stored a computer program for calculating an upper bound of the time required to transmit a multi frame real-time flow along a route in a multihop network, the computer program comprising instructions for causing a computer to:

receive input selecting the route in the multihop network, wherein the multiframe real-time flow is capable of being transmitted along the route, the route comprising a source node in the multihop network, a destination node in the multihop network, and at least one intermediate node in the multihop network, the source node comprising either an IP-endhost or an IP-router, the destination node comprising either an IP-endhost or an IP-router, and the multiframe flow comprising one or more frames; and

calculate an upper bound of the time required to transmit the multiframe real-time flow from the source node to the destination node along the route.

97. The computer-readable medium of claim 96, wherein determining the upper bound of the time required to transmit the multiframe real-time flow comprises:

determining a response time required to transmit the frame of the multiframe real-time flow across a first hop of the route, wherein the first hop comprises a link from the source node to a successive node, wherein the determining comprises calculating a formula according to

R_i<sup>k,link(S,succ(τ

i,S))</sup>=(max<sub>q=0 . . . Qik−

1</sub>R_i<sup>k,link(S,succ(τ

i,S))</sup>(q))+prop(S,succ(τ

^i,S))

where Q_i^k is defined as;

98. The computer-readable medium of claim 97, wherein determining the response time comprises determining transmission times for all the Ethernet frames comprising the frame of the multiframe real-time flow, according to the speed of the link for transmitting an Ethernet frame.

99. The computer-readable medium of claim 98, wherein determining the response time comprises determining generalized jitter for each of the Ethernet frames comprising the frame of the multiframe real-time flow as each Ethernet frame is transmitted across the first hop.

100. The computer-readable medium of claim 97, wherein determining the upper hound of the time required to transmit the multi frame real-time flow further comprises determining the response time required to transmit a frame of the multi frame real-time flow across a non-first hop of the route.

101. The computer-readable medium of claim 100, wherein determining the response time required to transmit a frame of the multiframe real-time flow across a non-first hop comprises:

determining a first response time, wherein the determining comprises calculating a formula according to

R_i^k,in(N)=(max<sub>q=0 . . . Qik−

1</sub>R_i^k,in(N)(q))

and wherein the first response time is measured from the moment when all Ethernet frames comprising the frame of the multiframe real-time flow have been received at a first node until the moment when all the Ethernet frames have been enqueued in the correct priority queue in the first node; and

determining a second response time, wherein the determining comprises calculating a formula according to

R_i<sup>k,link(N,succ(τ

i,N)</sup>=(max<sub>q=0 . . . Qik−

1</sub>R_i<sup>k,link(N,succ(τ

i,N))</sup>(q))+prop(S,succ(τ

_i,N))

and wherein the second response time is measured from the moment when all Ethernet frames comprising the frame of the multiframe real-time flow have been enqueued in the correct priority queue in the first node until the moment when all the Ethernet frames have been received at a successive node.

102. The computer-readable medium of claim 101, wherein determining the first response time comprises determining generalized jitter for each of the Ethernet frames.

103. The computer-readable medium of claim 101, wherein determining the second response time comprises:

determining transmission times for all the Ethernet frames, according to the speed of the link for transmitting an Ethernet frame; and

determining generalized jitter for each of the Ethernet frames.

104. A system for calculating an upper hound of the time required to transmit a multiframe real-time flow along a route in a multihop network, the system comprising:

a memory; and

a processor,

wherein the memory is encoded with instructions that, when executed, cause the processor to;

receive input selecting the route in the multihop network, wherein the multiframe real-time flow is capable of being transmitted along the route, the route comprising a source node in the multihop network, a destination node in the multihop network, and at least one intermediate node in the multihop network, the source node comprising either an IP-endhost or an IP-router, the destination node comprising either an IP-endhost or an IP-router, and the multiframe flow comprising one or more frames; and

calculate an upper bound of the time required to transmit the multiframe real-time flow from the source node to the destination node along the route.

105. The system of claim 104, wherein the memory is further encoded with instructions to determine whether it is possible to offer a delay guarantee for the multi frame real-time flow, wherein the delay conforms to a specified deadline for the arrival of the multiframe real-time flow at the destination node, given the upper bound of the time required to transmit the multiframe real-time flow from the source node to the destination node along the route.

106. The system of claim 105, wherein the memory is further encoded with instructions to if it is possible to offer the delay guarantee for transmission of the multiframe real-time flow along the route, transmit the multiframe real-time flow along the route.

107. The system of claim 105, wherein the memory is further encoded with instructions to if it is possible to offer the delay guarantee for transmission of the multiframe real-time flow along the route, allow transmission of the multiframe real-time flow.

108. The system of claim 105, wherein the memory is further encoded with instructions to if it is not possible to offer the delay guarantee for transmission of the multiframe real-time flow along the route, deny transmission of the multiframe real-time flow.

109. The system of claim 105, wherein the memory is further encoded with instructions to schedule transmission of the multiframe real-time flow at a particular time, wherein the time at which transmission of the multiframe real-time flow is scheduled is based at least in part upon the determination of whether it is possible to offer the delay guarantee for transmission of the multiframe real-time flow along the route.

110. The system of claim 105, wherein the memory is further encoded with, instructions to queue transmission of the multiframe real-time flow, wherein queuing is performed in a manner based at least in part upon the determination of whether it is possible to offer the delay guarantee for transmission of the multiframe real-time flow along the route.

111. The system of claim 110, wherein queuing transmission of the multiframe real-time flow is performed in a manner based at least in part upon the priority of the multiframe real-time flow.

112. The system of claim 105, wherein the memory is further encoded with instructions to:

if it is not possible to offer the delay guarantee for the multiframe real-time flow, determine whether there is a second route in the multihop network along which the multiframe real-time flow could be transmitted from the source node to the destination node; and

if a second route exists, determine an upper bound of the time required to transmit the multiframe real-time flow from the source node to the destination node along the second route, wherein the upper bound includes delay attributable to generalized jitter.

113. The system of claim 105, wherein the memory is further encoded with instructions to transmit a message, based upon the determination of whether it is possible to offer the delay guarantee for transmission of the multiframe real-time flow along the route.

114. The system of claim 104, wherein the instructions to determine the upper bound of the time required to transmit the multiframe real-time flow comprise instruct ions to:

determine a response time required to transmit the frame of the multi frame real-time flow across a first hop of the route, wherein the first hop comprises a link from the source node to a successive node, wherein the determining comprises calculating a formula according to

R_i<sup>k,link(S,succ(τ

i,S))</sup>=(max_{q=0 . . . Qik1-}R_i<sup>k,link(S,succ(τ

i,S))</sup>(q))+prop(S,succ(τ

_i,S))

where Q_i^k is defined as;

115. The system of claim 114, wherein the instructions for determining the response time comprise instructions to determine transmission times for all the Ethernet frames comprising the frame of the multiframe real-time flow, according to the speed of the link for transmitting an Ethernet frame.

116. The system of claim 114, wherein the instructions for determining the response time comprise instructions to determine generalized jitter for each of the Ethernet frames comprising the frame of the multiframe real-time flow as each Ethernet frame is transmitted across the first hop.

117. The system of claim 104, wherein the instructions for determining the upper bound of the time required to transmit the multi frame real-time flow further comprise instructions to determine the response time required to transmit a frame of the multiframe real-time flow across a non-first hop of the route.

118. The system of claim 117, wherein the instructions for determining the response time required to transmit a frame of the multiframe real-time flow across a non-first hop comprise instructions to:

determine a first response time, wherein the determining comprises calculating a formula according to

R_i^k,in(N)=(max<sub>q=0 . . . Qik−

1</sub>R_i^k,in(N)(q))

and wherein the first response time is measured from the moment when all Ethernet frames comprising the frame of the multiframe real-time flow have been received at a first node until the moment when all the Ethernet frames have been enqueued in the correct priority queue in the first node; and

determining a second response time, wherein the determining comprises calculating a formula according to

R_i<sup>k,link(N,succ(τ

i,N)</sup>=(max<sub>q=0 . . . Qik−

1</sub>R_i<sup>k,link(N,succ(τ

i,N))</sup>(q))+prop(S,succ(τ

_i, N))

and wherein the second response time is measured from the moment when all Ethernet frames comprising the frame of the multi frame real-time flow have been enqueued in the correct priority queue in the first node until the moment when all the Ethernet frames have been received at a successive node.

119. The system of claim 118, wherein the instructions for determining the first response time further comprise instructions to determine generalized jitter for each of the Ethernet frames.

120. The system of claim 118, wherein the instructions for determining the second response time further comprise instructions to:

determine transmission times for all the Ethernet frames, according to the speed of the link for transmitting an Ethernet frame; and

determine generalized jitter for each of the Ethernet frames.