DESCRIPTION
NODE DEVICE USED IN DISRUPTION/DELAY/DI SCONNECT
TOLERANT NETWORK AND COMMUNICATION ME THOD
5
Te c h n i c a l Fi e l d
[ 0 0 0 1 ]
Th e p r e s e n t i n v e n t i o n r e l a t e s t o a c ommu n i c a t i o n n o d e u s e d i n a
Di s r u p t i o n /De l a y/Di s c o n n e c t To l e r a n t Ne two r k a n d i t s c ommu n i c a t i o n
10 me t h o d .
Ba ck g r o u n d Ar t
[ 0 0 0 2 ]
A Di s r u p t i o n To l e r a n t Ne two r k i s a wi r e l e s s mu l t i - h o p n e two r k
i n c l u d i n g a p l u r a l i t y o f c ommu n i c a t i o n n o d e s . Th e Di s r u p t i o n To l e r a n t
15 Ne two r k c a n b e r e g a r d e d a s a De l a y To l e r a n t Ne two r k a n d a s a
Di s c o n n e c t To l e r a n t Ne two r k . Di s r u p t i o n /De l a y /Di s c o n n e c t To l e r a n t
Ne two r k s a r e h e r e i n r e f e r r e d t o c o l l e c t i v e l y a s "DTN" . I n a DTN, a
n umb e r o f c ommu n i c a t i o n n o d e s ( h e r e i n a f t e r r e f e r r e d t o a s "DTN
n o d e s " ) a u t o n omo u s l y r e l a y a me s s a g e ( d a t a b u n d l e o r d a t a p a c k e t ) ,
20 t h e r e b y a c h i e v i n g t h e d e l i v e r y o f t h e me s s a g e f r om a s o u r c e n o d e t o a
d e s t i n a t i o n n o d e . On e o r b o t h o f t h e s o u r c e n o d e a n d t h e d e s t i n a t i o n
n o d e ma y b e l o n g t o t h e DTN ( i . e . , DTN n o d e s ) o r b e l o n g t o a n e x t e r n a l
n e two r k ( e . g . , t h e I n t e r n e t , a p u b l i c c e l l u l a r n e two r k , o r a wi r e l e s s
Lo c a l Ar e a Ne two r k ( LAN) ) . I f o n e o r b o t h o f t h e s o u r c e n o d e a n d t h e
25 d e s t i n a t i o n n o d e b e l o n g t o a n e x t e r n a l n e two r k , a n y o n e o f t h e DTN
n o d e s s e r v e s a s a r o u t e r o r a g a t ewa y t h a t r e l a ys me s s a g e s b e twe e n t h e
DTN a n d t h e e x t e r n a l n e two r k .
[ 0 0 0 3 ]
Th e DTN i s b a s e d o n t h e p r emi s e t h a t a t emp o r a r y o r
30 i n t e rmi t t e n t c ommu n i c a t i o n d i s c o n n e c t i o n c o u l d o c c u r d u e t o
mo v eme n t o f DTN n o d e s , b l o c k i n g o f wi r e l e s s s i g n a l s c a u s e d b y a n
o b s t a c l e , o r t h e l i k e . I n o t h e r wo r d s , t h e DTN i s b a s e d o n t h e p r emi s e
t h a t a t l e a s t a t s ome p o i n t i n t ime , t h e r e i s n o s t a b l e c ommu n i c a t i o n
3
p a t h b e twe e n t h e s o u r c e n o d e a n d t h e d e s t i n a t i o n n o d e . To c o p e wi t h
t h e t emp o r a r y o r i n t e rmi t t e n t c ommu n i c a t i o n d i s c o n n e c t i o n , e a c h DTN
n o d e p e r f o rms a s t o r e - a n d - f o rwa r d o p e r a t i o n . Ac c o r d i n g l y , t h e DTN
c a n a l s o b e r e g a r d e d a s a s t o r e - a n d - f o rwa r d t yp e wi r e l e s s mu l t i - h o p
n e two r k . Fu r t h e r , s ome o r a l l o f t h e p l u r a l i t y o f DTN n o d 5 e s
c o n s t i t u t i n g t h e DTN ma y b e mo b i l e t e rmi n a l s h a v i n g mo b i l i t y . I n t h i s
r e g a r d , t h e DTN c a n a l s o b e r e g a r d e d a s a s t o r e - and- f o rwa r d t y p e
wi r e l e s s a d - h o c n e two r k . Fo r e x amp l e , i t h a s b e e n a s s ume d t h a t t h e
DTN i s u s e d f o r eme r g e n c y c ommu n i c a t i o n s a t t h e t ime o f a d i s a s t e r ,
10 a n d i n t e r - v e h i c l e c ommu n i c a t i o n s a n d r o a d - t o - v e h i c l e c ommu n i c a t i o n s
i n I n t e l l i g e n t Tr a n s p o r t S ys t ems ( IT S ) .
[ 0 0 0 4 ]
As d e s c r i b e d a b o v e , a DTN n o d e p e r f o rms a s t o r e - a n d - f o rwa r d
o p e r a t i o n . Th a t i s , a DTN n o d e t emp o r a r i l y s t o r e s me s s a g e s , r e c e i v e d
15 f r om a c e r t a i n DTN n o d e a n d a r e d e s t i n e d f o r a d e s t i n a t i o n n o d e , i n a
memo r y ( h e r e i n a f t e r c a l l e d "me s s a g e b u f f e r " ) . Th e n , wh e n
c ommu n i c a t i o n wi t h o t h e r DTN n o d e s b e c ome s p o s s i b l e , t h e DTN n o d e
d e t e rmi n e s a f o rwa r d i n g d e s t i n a t i o n a n d a me s s a g e ( s ) t o b e f o rwa r d e d
t h e r e t o i n a c c o r d a n c e wi t h a r o u t i n g p r o t o c o l a n d f o rwa r d s t h e
20 me s s a g e ( s ) s t o r e d i n t h e me s s a g e b u f f e r t o t h e d e t e rmi n e d f o rwa r d i n g
d e s t i n a t i o n .
[ 0 0 0 5 ]
Va r i o u s p r o p o s a l s f o r a r o u t i n g p r o t o c o l s u i t a b l e f o r t h e DTN
h a v e b e e n ma d e . Ep i d emi c r o u t i n g , S p r a y a n d Wa i t , a n d PROPHET
25 h a v e b e e n k n own a s t yp i c a l r o u t i n g p r o t o c o l s f o r t h e DTN. Th e
PROPHET i s a n a b b r e v i a t i o n f o r " P r o b a b i l i s t i c Ro u t i n g P r o t o c o l u s i n g
Hi s t o r y o f En c o u n t e r s a n d Tr a n s i t i v i t y" . Th e Ep i d emi c r o u t i n g a n d t h e
S p r a y a n d Wa i t d o n o t u s e a n y i n f o rma t i o n a b o u t a n e two r k s t a t e . I n
c o n t r a s t t o t h i s , i n t h e PROPHET, e a c h DTN n o d e s t o r e s a h i s t o r y o f
30 c o n t a c t s i n t h e p a s t a n d u s e s t h i s h i s t o r y t o d e t e rmi n e t h e f o rwa r d i n g
d e s t i n a t i o n o f a me s s a g e .
[ 0 0 0 6 ]
Th e Ep i d emi c r o u t i n g i s a n imp r o v e d v e r s i o n o f t h e p r imi t i v e
f l o o d i n g me c h a n i sm. S p e c i f i c a l l y, e a c h DTN n o d e t h a t s u p p o r t s t h e
4
Ep i d emi c r o u t i n g ma n a g e s i n f o rma t i o n c a l l e d a " s umma r y v e c t o r " . Th e
s umma r y v e c t o r i n d i c a t e s i d e n t i f i e r s o f me s s a g e s t h a t h a v e b e e n s t o r e d
i n t h e me s s a g e b u f f e r o f e a c h DTN n o d e . Du r i n g a c o n t a c t wi t h a n
a d j a c e n t DTN n o d e , e a c h DTN n o d e e x c h a n g e s r e s p e c t i v e s umma r y
v e c t o r s wi t h t h e a d j a c e n t DTN n o d e , i d e n t i f i e s a me s s a g e ( s ) t h a t i s n 5 o t
p o s s e s s e d b y t h a t DTN n o d e i t s e l f , a n d r e c e i v e s t h e i d e n t i f i e d
me s s a g e ( s ) f r om t h e a d j a c e n t DTN n o d e .
[ 0 0 0 7 ]
Th e S p r a y a n d Wa i t i s a n imp r o v e d v e r s i o n o f t h e Ep i d emi c
10 r o u t i n g . S imi l a r l y t o t h e DTN n o d e i n t h e Ep i d emi c r o u t i n g , d u r i n g
c o n t a c t wi t h a n a d j a c e n t DTN n o d e , e a c h DTN n o d e e x c h a n g e s
r e s p e c t i v e s umma r y v e c t o r s wi t h t h e a d j a c e n t DTN n o d e a n d r e c e i v e s a
me s s a g e ( s ) t h a t i s n o t p o s s e s s e d b y t h a t DTN n o d e i t s e l f f r om t h e
a d j a c e n t DTN n o d e . I n t h e S p r a y a n d Wa i t , wh e n a me s s a g e i s
15 g e n e r a t e d i n t h e s o u r c e n o d e , t h e ma x imum n umb e r o f r e p l i c a t i o n s o f
t h a t me s s a g e a l l owe d t o t h e DTN i s s p e c i f i e d . I n t h e S p r a y s t a g e , t h e
DTN n o d e t h a t p o s s e s s e s t h e me s s a g e g e n e r a t e s c o p i e s o f t h e me s s a g e
u n t i l t h e n umb e r o f r e p l i c a t i o n s r e a c h e s t h e s p e c i f i e d ma x imum n umb e r ,
a n d g i v e s c o p i e s o f t h e me s s a g e t o o t h e r DTN n o d e s wh i c h t h e DTN
20 n o d e h a s e n c o u n t e r e d . Wh e n t h e n umb e r o f r e p l i c a t i o n s r e a c h e s t h e
s p e c i f i e d ma x imum n umb e r (Wa i t s t a g e ) , t h e DTN n o d e h o l d s t h e
me s s a g e wi t h o u t s e n d i n g c o p i e s o f t h a t me s s a g e t o o t h e r DTN n o d e s ,
a n d o n l y wh e n t h e DTN n o d e p o s s e s s i n g t h e me s s a g e h a s e n c o u n t e r e d
t h e f i n a l d e s t i n a t i o n n o d e , t h e DTN n o d e s e n d s t h e me s s a g e t o t h e f i n a l
25 d e s t i n a t i o n n o d e .
[ 0 0 0 8 ]
I n t h e PROPHET, e a c h DTN n o d e e x c h a n g e s me t r i c s c a l l e d
"De l i v e r y P r e d i c t a b i l i t y" i n a d d i t i o n t o t h e s umma r y v e c t o r s wi t h a n
a d j a c e n t DTN n o d e . A De l i v e r y P r e d i c t a b i l i t y P (A, B) i n d i c a t e s a
30 p r o b a b i l i t y t h a t a DTN n o d e A c a n d e l i v e r a me s s a g e t o a DTN n o d e B.
Fo r e x amp l e , i n t h e c a s e wh e r e a n o d e A c o n t a c t s wi t h a n o d e B, o n l y
wh e n t h e n o d e B h a s a De l i v e r y P r e d i c t a b i l i t y f o r a d e s t i n a t i o n n o d e D
h i g h e r t h a n t h a t o f t h e n o d e A ( i . e . , o n l y wh e n P (B, D) i s h i g h e r t h a n
P (A, D) ) , t h e n o d e A s e n d s a me s s a g e a d d r e s s e d t o t h e d e s t i n a t i o n n o d e
5
D t o t h e n o d e B.
[ 0 0 0 9 ]
P a t e n t Li t e r a t u r e 1 d i s c l o s e s a n imp r o v eme n t i n a me s s a g e
d e l i v e r y b e twe e n DTN n o d e s . P a t e n t Li t e r a t u r e 2 d i s c l o s e s a n
imp r o v eme n t i n r o u t i n g i n a DTN5 .
Ci t a t i o n Li s t
Pa t e n t Li t e r a t u r e
[0010]
[ P a t e n t Li t e r a t u r e 1 ] I n t e r n a t i o n a l Ap p l i c a t i o n P u b l i c a t i o n No . WO
10 2 0 1 1 / 0 7 1 0 4 5
[ P a t e n t Li t e r a t u r e 2 ] I n t e r n a t i o n a l Ap p l i c a t i o n P u b l i c a t i o n No . WO
2 0 1 3 / 0 7 6 9 1 2
S umma r y o f I n v e n t i o n
Te c h n i c a l Pr o b l em
15 [0011]
S imi l a r l y t o t h e a b o v e - d e s c r i b e d Ep i d emi c r o u t i n g , t h e S p r a y
a n d Wa i t , a n d t h e PROPHET , mo s t o f r o u t i n g p r o t o c o l s f o r t h e DTN
g e n e r a t e a n umb e r o f c o p i e s o f a me s s a g e a n d s p r e a d a n umb e r o f t h e s e
c o p i e s o f t h e me s s a g e wi t h i n t h e DTN. Th e r e f o r e , e v e n a f t e r o n e o f
20 t h e c o p i e s o f t h e me s s a g e a r r i v e s a t t h e f i n a l d e s t i n a t i o n n o d e , a
n umb e r o f r ema i n i n g c o p i e s o f t h e me s s a g e , e a c h o f wh i c h c o n t a i n s t h e
s ame c o n t e n t a s t h a t o f t h e a r r i v e d me s s a g e , a r e f u r t h e r s p r e a d wi t h i n
t h e DTN. As a r e s u l t , a c o p y o f t h e me s s a g e , wh i c h h a s a l r e a d y
a r r i v e d a t t h e f i n a l d e s t i n a t i o n n o d e , r ema i n s i n e a c h DTN n o d e . I n
25 o r d e r t o i n c r e a s e a me s s a g e d e l i v e r y s u c c e s s r a t e i n a DTN, i t i s
d e s i r a b l e t o d e l e t e c o p i e s o f a me s s a g e t h a t h a s a l r e a d y a r r i v e d a t t h e
d e s t i n a t i o n n o d e a n d p r e v e n t t h em f r om b e i n g s p r e a d wi t h i n t h e DTN.
P a t e n t Li t e r a t u r e 1 a n d 2 f a i l t o d i s c l o s e a n y t e c h n i q u e f o r c o p i n g wi t h
t h e a b o v e p r o b l em.
30 [0012]
Ac c o r d i n g l y , a n o b j e c t o f t h e p r e s e n t i n v e n t i o n i s t o p r o v i d e a
n o d e d e v i c e , a c ommu n i c a t i o n me t h o d , a n d a p r o g r am c a p a b l e o f
p r e v e n t i n g c o p i e s o f a me s s a g e t h a t h a s a l r e a d y a r r i v e d a t i t s f i n a l
des t i n a t i o n n o d e f r om b e i n g s p r e a d wi t h i n a DTN .
6
S o l u t i o n t o Pr o b l em
[ 0 0 1 3 ]
I n a f i r s t e x emp l a r y a s p e c t , a n o d e d e v i c e u s e d i n a
Di s r u p t i o n /De l a y/Di s c o n n e c t To l e r a n t Ne two r k (DTN) i n c l u d e s a
c ommu n i c a t i o n u n i t a n d a f i r s t me s s a g e b u f f e r . Th e c ommu n i c a t i 5 o n
u n i t i s c o n f i g u r e d t o c ommu n i c a t e wi t h a n a d j a c e n t n o d e i n t h e DTN.
Th e me s s a g e b u f f e r i s c o n f i g u r e d t o s t o r e a p l u r a l i t y o f me s s a g e s
t r a n s f e r r e d t h r o u g h t h e DTN. Fu r t h e r , t h e c ommu n i c a t i o n u n i t i s
c o n f i g u r e d t o ma n a g e a f i r s t s umma r y v e c t o r a n d a n Ac k n o wl e d g eme n t
10 (ACK) l i s t , a n d a l s o c o n f i g u r e d t o r e c e i v e a s e c o n d ACK l i s t ma n a g e d
b y t h e a d j a c e n t n o d e d u r i n g c o n t a c t wi t h t h e a d j a c e n t n o d e a n d u p d a t e
t h e f i r s t ACK l i s t a n d t h e f i r s t s umma r y v e c t o r b a s e d o n t h e s e c o n d
ACK l i s t . Th e f i r s t s umma r y v e c t o r i n d i c a t e s o n e o r mo r e s t o r e d
me s s a g e s t h a t h a v e b e e n s t o r e d i n t h e f i r s t me s s a g e b u f f e r . Du r i n g t h e
15 c o n t a c t wi t h t h e a d j a c e n t n o d e , t h e f i r s t s umma r y v e c t o r i s s e n t t o t h e
a d j a c e n t n o d e p r i o r t o t r a n smi s s i o n o f t h e o n e o r mo r e s t o r e d me s s a g e s .
Th e f i r s t ACK l i s t i n d i c a t e s o n e o r mo r e ACK me s s a g e s t h a t h a v e b e e n
r e c o g n i z e d b y t h e n o d e d e v i c e . Th e s e c o n d ACK l i s t i n d i c a t e s o n e o r
mo r e ACK me s s a g e s t h a t h a v e b e e n r e c o g n i z e d b y t h e a d j a c e n t n o d e .
20 Ea c h o f t h e o n e o r mo r e ACK me s s a g e s i n d i c a t e s a n a l r e a d y - d e l i v e r e d
me s s a g e t h a t h a s a l r e a d y b e e n d e l i v e r e d t o a f i n a l d e s t i n a t i o n n o d e
t h r o u g h t h e DTN.
[ 0 0 1 4 ]
I n a s e c o n d e x emp l a r y a s p e c t , a c ommu n i c a t i o n me t h o d ,
25 p e r f o rme d b y a n o d e d e v i c e u s e d i n a Di s r u p t i o n /De l a y /Di s c o n n e c t
To l e r a n t Ne two r k (DTN) , i n c l u d e s : ( a ) r e c e i v i n g a s e c o n d ACK l i s t
ma n a g e d b y a n a d j a c e n t n o d e d u r i n g c o n t a c t wi t h t h e a d j a c e n t n o d e ;
a n d ( b ) u p d a t i n g a f i r s t ACK l i s t a n d a f i r s t s umma r y v e c t o r b a s e d o n
t h e s e c o n d ACK l i s t , t h e f i r s t ACK l i s t a n d t h e f i r s t s umma r y v e c t o r
30 b e i n g ma n a g e d b y t h e n o d e d e v i c e . Th e f i r s t s umma r y v e c t o r i n d i c a t e s
o n e o r mo r e s t o r e d me s s a g e s t h a t h a v e b e e n s t o r e d i n t h e f i r s t me s s a g e
b u f f e r . Du r i n g t h e c o n t a c t wi t h t h e a d j a c e n t n o d e , t h e f i r s t s umma r y
v e c t o r i s s e n t t o t h e a d j a c e n t n o d e p r i o r t o t r a n smi s s i o n o f t h e o n e o r
mo r e s t o r e d me s s a g e s . Th e f i r s t ACK l i s t i n d i c a t e s o n e o r mo r e ACK
7
me s s a g e s t h a t h a v e b e e n r e c o g n i z e d b y t h e n o d e d e v i c e . Th e s e c o n d
ACK l i s t i n d i c a t e s o n e o r mo r e ACK me s s a g e s t h a t h a v e b e e n
r e c o g n i z e d b y t h e a d j a c e n t n o d e . Ea c h o f t h e o n e o r mo r e ACK
me s s a g e s i n d i c a t e s a n a l r e a d y - d e l i v e r e d me s s a g e t h a t h a s a l r e a d y b e e n
d e l i v e r e d t o a f i n a l d e s t i n a t i o n n o d e t h r o u g h t h e DTN5 .
[ 0 0 1 5 ]
I n a t h i r d e x emp l a r y a s p e c t , a p r o g r am i n c l u d e s i n s t r u c t i o n s f o r
c a u s i n g a c omp u t e r t o p e r f o rm t h e a b o v e - d e s c r i b e d c ommu n i c a t i o n
me t h o d a c c o r d i n g t o t h e s e c o n d e x emp l a r y a s p e c t .
10 Ad v a n t a g eous Ef f e c t s o f I n v en t i o n
[ 0 0 1 6 ]
Ac c o r d i n g t o a s p e c t s s t a t e d a b o v e , i t i s p o s s i b l e t o p r o v i d e a
n o d e d e v i c e , a c ommu n i c a t i o n me t h o d , a n d a p r o g r am c a p a b l e o f
p r e v e n t i n g c o p i e s o f a me s s a g e t h a t h a s a l r e a d y a r r i v e d a t i t s f i n a l
15 d e s t i n a t i o n n o d e f r om b e i n g s p r e a d wi t h i n a DTN .
Br i e f De s c r i p t i o n o f Dr awi n g s
[ 0 0 1 7 ]
Fi g . 1 s h ows a c o n f i g u r a t i o n e x amp l e o f a DTN a c c o r d i n g t o a
f i r s t e x emp l a r y emb o d ime n t ;
20 Fi g . 2 i s a b l o c k d i a g r am s h owi n g a c o n f i g u r a t i o n e x amp l e o f a
DTN n o d e a c c o r d i n g t o t h e f i r s t e x emp l a r y emb o d ime n t ;
Fi g . 3 s h ows a n e x amp l e o f a s umma r y v e c t o r ;
Fi g . 4 s h ows a n e x amp l e o f a n ACK l i s t ;
Fi g . 5 i s a s e q u e n c e d i a g r am s h owi n g a n e x amp l e o f a
25 c ommu n i c a t i o n p r o c e d u r e o f a DTN n o d e a c c o r d i n g t o t h e f i r s t
e x emp l a r y emb o d ime n t ;
Fi g . 6 i s a s e q u e n c e d i a g r am s h owi n g a n e x amp l e o f a
c ommu n i c a t i o n p r o c e d u r e o f a DTN n o d e a c c o r d i n g t o a s e c o n d
e x emp l a r y emb o d ime n t ;
30 Fi g . 7 i s a s e q u e n c e d i a g r am s h owi n g a n e x amp l e o f a
c ommu n i c a t i o n p r o c e d u r e o f a DTN n o d e a c c o r d i n g t o a t h i r d
e x emp l a r y emb o d ime n t ;
Fi g . 8 s h ows a n e x amp l e o f a s umma r y v e c t o r i n c l u d i n g a n ACK
a c c o r d i n g t o a f o u r t h e x emp l a r y emb o d ime n t ; a n d
8
Fi g . 9 s h ows a n e x amp l e o f a s umma r y v e c t o r i n c l u d i n g a n ACK
a c c o r d i n g t o t h e f o u r t h e x emp l a r y emb o d ime n t .
De s c r i p t i o n o f Emb o d ime n t s
[ 0 0 1 8 ]
S p e c i f i c e x emp l a r y emb o d ime n t s a r e e x p l a i n e d h e r e i n a f t e r i 5 n
d e t a i l wi t h r e f e r e n c e t o t h e d r awi n g s . Th e s ame s ymb o l s a r e a s s i g n e d
t o t h e s ame o r c o r r e s p o n d i n g e l eme n t s t h r o u g h o u t t h e d r awi n g s , a n d
dup l i c a t e d e x p l a n a t i o n s a r e omi t t e d a s n e c e s s a r y.
[ 0 0 1 9 ]
10 Fi r s t e x emp l a r y emb o d ime n t
Fi g . 1 s h ows a c o n f i g u r a t i o n e x amp l e o f a
Di s r u p t i o n /De l a y/Di s c o n n e c t To l e r a n t Ne two r k (DTN) 1 0 0 a c c o r d i n g t o
t h i s e x emp l a r y emb o d ime n t . Th e DTN 1 0 0 i n c l u d e s DTN n o d e s 1 . Th e
DTN n o d e s 1 a u t o n omo u s l y r e l a y a me s s a g e ( d a t a b u n d l e o r d a t a
15 p a c k e t ) , t h e r e b y a c h i e v i n g t h e d e l i v e r y o f t h e me s s a g e f r om a s o u r c e
n o d e t o a d e s t i n a t i o n n o d e .
[0020]
Ea c h DTN n o d e 1 ma y b e a mo b i l e t e rmi n a l h a v i n g mo b i l i t y ( e . g . ,
a c e l l u l a r p h o n e , a sma r t p h o n e , a t a b l e t c omp u t e r , a p e r s o n a l c omp u t e r
20 ( PC) ) . Ea c h DTN n o d e 1 ma y b e a c ommu n i c a t i o n t e rmi n a l i n s t a l l e d i n
a t r a n s p o r t d e v i c e s u c h a s a n a u t omo b i l e , a n a i r p l a n e , a r a i l r o a d
v e h i c l e , a n d a s h i p . S ome o f t h e DTN n o d e s 1 , h owe v e r , ma y b e f i x e d
wir e l e s s t e rmi n a l s s u c h a s wi r e l e s s LAN a c c e s s p o i n t s .
[0021]
25 Ea c h DTN n o d e 1 p e r f o rms a s t o r e - a n d - f o rwa r d o p e r a t i o n . Th a t
i s , e a c h DTN n o d e 1 i n c l u d e s a me s s a g e b u f f e r f o r s t o r i n g me s s a g e s
t h a t a r e t r a n s f e r r e d t h r o u g h t h e DTN 1 0 0 . Ea c h DTN n o d e 1
t emp o r a r i l y s t o r e s , i n t h e me s s a g e b u f f e r , me s s a g e s t h a t h a v e b e e n
r e c e i v e d f r om o t h e r DTN n o d e s . Th e n , wh e n c ommu n i c a t i o n wi t h o t h e r
30 DTN n o d e s b e c ome s p o s s i b l e , t h e DTN n o d e 1 d e t e rmi n e s a f o rwa r d i n g
d e s t i n a t i o n a n d a me s s a g e ( s ) t o b e f o rwa r d e d t h e r e t o i n a c c o r d a n c e
wi t h a r o u t i n g p r o t o c o l a n d s e n d s t h e me s s a g e ( s ) s t o r e d i n t h e me s s a g e
b u f f e r t o t h e d e t e rmi n e d f o rwa r d i n g d e s t i n a t i o n .
[0022]
9
Th e r o u t i n g p r o t o c o l u s e d i n t h i s e x emp l a r y emb o d ime n t i s a n y
p r o t o c o l i n wh i c h a s umma r y v e c t o r i s u s e d . Th e r o u t i n g p r o t o c o l ma y
be Ep i d emi c r o u t i n g , S p r a y a n d Wa i t , PROPHET, o r a p r o t o c o l
imp r o v e d t h e r e o f . Ra c h DTN n o d e 1 ma n a g e s a s umma r y v e c t o r , wh i c h
i n d i c a t e s i d e n t i f i e r s o f me s s a g e s t h a t h a v e b e e n s t o r e d i n t h e me s s a 5 g e
b u f f e r o f t h e DTN n o d e 1 . Du r i n g c o n t a c t wi t h a n a d j a c e n t DTN n o d e ,
t h e s umma r y v e c t o r i s s e n t p r i o r t o t h e t r a n smi s s i o n o f t h e me s s a g e s ,
wh i c h h a v e s t o r e d i n t h e me s s a g e b u f f e r . Th a t i s , d u r i n g c o n t a c t wi t h
a n a d j a c e n t DTN n o d e , e a c h DTN n o d e 1 e x c h a n g e s s umma r y v e c t o r s
10 wi t h a n a d j a c e n t DTN n o d e , i d e n t i f i e s a me s s a g e ( s ) t h a t i s n o t
p o s s e s s e d b y t h a t DTN n o d e i t s e l f , a n d a c q u i r e s t h e i d e n t i f i e d
me s s a g e ( s ) f r om t h e a d j a c e n t DTN n o d e .
[0023]
Fi g . 2 s h ows a n e x amp l e o f a s t r u c t u r e o f a s umma r y v e c t o r . A
15 s umma r y v e c t o r 2 0 s h own i n Fi g . 2 i n c l u d e s a n o d e ID 2 0 0 a n d N
n umb e r o f me s s a g e IDs 2 0 1 . Th e n o d e ID 2 0 0 i n d i c a t e s a n i d e n t i f i e r ,
e . g . , a n i n t e r n e t p r o t o c o l ( I P ) a d d r e s s , o f t h e DTN n o d e 1 t h a t ma n a g e s
t h e s umma r y v e c t o r 2 0 . Ea c h o f t h e N me s s a g e IDs 2 0 1 i n d i c a t e s a n
i d e n t i f i e r o f a me s s a g e t h a t h a s b e e n s t o r e d i n t h e me s s a g e b u f f e r o f
20 t h e DTN n o d e 1 ma n a g i n g t h e s umma r y v e c t o r 2 0 . Fo r e x amp l e , e a c h
me s s a g e ID 2 0 1 ma y b e s p e c i f i e d b y t h e c omb i n a t i o n o f t h e a d d r e s s o f
t h e s o u r c e n o d e , t h e a d d r e s s o f t h e d e s t i n a t i o n n o d e , a n d t h e s e q u e n c e
n umb e r o f t h e me s s a g e . Al t e r n a t i v e l y , e a c h me s s a g e ID 2 0 1 ma y b e a
h a s h v a l u e c a l c u l a t e d f r om t h e a d d r e s s o f t h e s o u r c e n o d e , t h e a d d r e s s
25 o f t h e d e s t i n a t i o n n o d e , a n d t h e s e q u e n c e n umb e r o f t h e me s s a g e s o
t h a t i t s d a t a s i z e i s r e d u c e d .
[0024]
Fu r t h e r , i n t h i s e x emp l a r y emb o d ime n t , e a c h DTN n o d e 1
ma n a g e s a n Ac k n owl e d g eme n t (ACK) l i s t i n a d d i t i o n t o t h e s umma r y
30 v e c t o r . Th e ACK l i s t i n d i c a t e s o n e o r mo r e ACK me s s a g e s t h a t h a v e
b e e n r e c o g n i z e d b y e a c h DTN n o d e 1 . Th e ACK me s s a g e i n d i c a t e s a n
a l r e a d y - d e l i v e r e d me s s a g e t h a t h a s a l r e a d y b e e n d e l i v e r e d t o t h e f i n a l
d e s t i n a t i o n n o d e t h r o u g h t h e DTN 1 0 0 .
[0025]
10
I n p r i n c i p l e , t h e ACK me s s a g e i s g e n e r a t e d b y t h e f i n a l
d e s t i n a t i o n n o d e . Wh e n each DTN n o d e 1 r e c e i v e s , t h r o u g h t h e DTN
1 0 0 , a me s s a g e i n wh i c h t h e DTN n o d e 1 i t s e l f i s d e s i g n a t e d a s t h e
f i n a l d e s t i n a t i o n , t h e DTN n o d e 1 ma y g e n e r a t e a n ACK me s s a g e
c o r r e s p o n d i n g t o t h a t me s s a g e a n d a d d t h e g e n e r a t e d ACK me s s a g e 5 t o
i t s own ACK l i s t .
[0026]
Th e d e s t i n a t i o n o f a me s s a g e t r a n s f e r r e d i n t h e DTN 1 0 0 c o u l d ,
h owe v e r , b e a n o d e t h a t b e l o n g s t o a n e x t e r n a l n e two r k ( e . g . , t h e
10 I n t e r n e t , a p u b l i c c e l l u l a r n e two r k , o r a wi r e l e s s Lo c a l Ar e a Ne two r k
( LAN) ) . Fu r t h e r , a DTN s e r v e r t h a t r e l a y s a me s s a g e b e twe e n DTNs
t h a t a r e p h y s i c a l l y a p a r t f r om e a c h o t h e r c o u l d b e u s e d . I n t h e s e c a s e s ,
a t l e a s t o n e o f t h e DTN n o d e s 1 s e r v e s a s a r o u t e r o r a g a t ewa y t h a t
r e l a y s a me s s a g e b e twe e n t h e DTN 1 0 0 a n d t h e e x t e r n a l n e two r k , o r
15 b e twe e n t h e DTN 1 0 0 a n d t h e DTN s e r v e r . Ac c o r d i n g l y , i n t h e s e c a s e s ,
wh e n a me s s a g e t o b e s e n t t o t h e o t h e r n e two r k o r t h e DTN s e r v e r h a s
a r r i v e d a t t h e DTN n o d e 1 t h a t s e r v e s a s t h e r o u t e r o r t h e g a t ewa y , t h a t
DTN n o d e 1 ma y g e n e r a t e a n ACK me s s a g e f o r t h e a r r i v e d me s s a g e . I n
o t h e r wo r d s , t h e DTN n o d e 1 t h a t s e r v e s a s t h e r o u t e r o r t h e g a t ewa y
20 c a n b e r e g a r d e d a s b e i n g t h e f i n a l d e s t i n a t i o n n o d e .
[0027]
Fi g . 3 s h ows a n e x amp l e o f a s t r u c t u r e o f a n ACK l i s t . An ACK
l i s t 3 0 s h own i n Fi g . 3 i n c l u d e s a n o d e ID 3 0 0 a n d M n umb e r o f
me s s a g e IDs 3 0 1 . Th e n o d e ID 3 0 0 i n d i c a t e s a n i d e n t i f i e r , e . g . , a n
25 i n t e r n e t p r o t o c o l ( IP ) a d d r e s s , o f t h e DTN n o d e 1 t h a t ma n a g e s t h e
ACK l i s t 3 0 . Ea c h o f t h e M me s s a g e IDs 3 0 1 c o r r e s p o n d s t o a n
i d e n t i f i e r o f a n ACK me s s a g e t h a t h a s b e e n r e c o g n i z e d b y t h e DTN
n o d e 1 ma n a g i n g t h e ACK l i s t 3 0 . Ea c h me s s a g e ID 3 0 1 ma y b e
d e f i n e d i n a ma n n e r s imi l a r t o t h a t b y wh i c h t h e me s s a g e IDs 2 0 1
30 i n c l u d e d i n t h e s umma r y v e c t o r 2 0 a r e d e f i n e d .
[0028]
Fu r t h e r , t h e ACK l i s t 3 0 ma y i n c l u d e i n f o rma t i o n f o r s p e c i f yi n g
t h e e x p i r a t i o n t ime o f e a c h ACK me s s a g e , e . g . , a Time -To- Li v e (TT L)
v a l u e o r a Time s -To- S e n d (TTS ) v a l u e . Th e Time -To-Li v e (TT L) v a l u e
11
s p e c i f i e s t h e u p p e r l imi t v a l u e f o r t h e n umb e r o f f o rwa r d i n g o p e r a t i o n s
( s o - c a l l e d " h o p n umb e r " ) wh e n a n ACK me s s a g e i s f o rwa r d e d amo n g
DTN n o d e s 1 . Th e TTS v a l u e s p e c i f i e s t h e u p p e r l imi t v a l u e f o r t h e
n umb e r o f f o rwa r d i n g o p e r a t i o n s f o r f o rwa r d i n g a n ACK me s s a g e t o
a n o t h e r DTN n o d e 1 p e r f o rme d b y o n e DTN n o d e ( t h a t i s , f o r t 5 h e
n umb e r o f r e p l i c a t i o n s o f a n ACK me s s a g e p e r f o rme d i n o n e DTN n o d e
1 ) . Al t e r n a t i v e l y , t h e i n f o rma t i o n f o r s p e c i f yi n g t h e e x p i r a t i o n t ime o f
each ACK me s s a g e ma y b e a c omb i n a t i o n o f i n f o rma t i o n i n d i c a t i n g t h e
g e n e r a t i o n t ime o f t h e ACK me s s a g e ( i . e . , t ime s t amp ) a n d i n f o rma t i o n
10 i n d i c a t i n g a n a v a i l a b l e p e r i o d ( i . e . , l i f e s p a n ) e x p r e s s e d i n s e c o n d s o r
i n mi n u t e s . Wh e n a l l t h e ACK me s s a g e s h a v e a c o mmo n a v a i l a b l e
p e r i o d ( l i f e s p a n ) , t h e ACK l i s t 3 0 ma y i n c l u d e o n l y t h e i n f o rma t i o n
i n d i c a t i n g t h e g e n e r a t i o n t ime o f t h e ACK me s s a g e ( t ime s t amp ) f o r
s p e c i f yi n g t h e e x p i r a t i o n t ime o f t h e ACK me s s a g e . Th e i n f o rma t i o n
15 f o r s p e c i f yi n g t h e e x p i r a t i o n t ime o f a n ACK me s s a g e a r e d e f i n e d
i n d e p e n d e n t l y o f t h e e x p i r a t i o n t ime o f a me s s a g e s t o r e d i n t h e
me s s a g e b u f f e r o f t h e DTN n o d e 1 ( e . g . , a TT L v a l u e , a TTS v a l u e , a
g e n e r a t i o n t ime , o r a c omb i n a t i o n o f a g e n e r a t i o n t ime a n d a l i f e s p a n ,
t h e s e i n f o rma t i o n e l eme n t s a r e h e l d i n t h e s umma r y v e c t o r 2 0 ) .
20 [0029]
Du r i n g c o n t a c t wi t h a n a d j a c e n t DTN n o d e , e a c h DTN n o d e 1
e x c h a n g e s t h e ACK l i s t s a s we l l a s t h e s umma r y v e c t o r s wi t h t h e
a d j a c e n t DTN n o d e . Fu r t h e r , e a c h DTN n o d e 1 u p d a t e s t h e ACK l i s t
h e l d b y t h a t DTN n o d e i t s e l f b a s e d o n t h e ACK l i s t r e c e i v e d f r om t h e
25 a d j a c e n t DTN n o d e . S p e c i f i c a l l y, e a c h DTN n o d e 1 ma y me r g e t h e
ACK l i s t h e l d b y i t s e l f wi t h t h e ACK l i s t r e c e i v e d f r om t h e a d j a c e n t
DTN n o d e . Wh e n e x p r e s s e d i n o t h e r wo r d s i n a c c o r d a n c e wi t h t h e s e t
t h e o r y, e a c h DTN n o d e 1 ma y o b t a i n t h e u n i o n o f t h e ACK l i s t h e l d b y
i t s e l f wi t h t h e ACK l i s t r e c e i v e d f r om t h e a d j a c e n t DTN n o d e .
30 [0030]
Fu r t h e r , e a c h DTN n o d e 1 u p d a t e s t h e s umma r y v e c t o r h e l d b y
t h a t DTN n o d e i t s e l f b a s e d o n t h e ACK l i s t r e c e i v e d f r om t h e a d j a c e n t
DTN n o d e . S p e c i f i c a l l y , e a c h DTN n o d e 1 ma y e l imi n a t e , f r om i t s own
s umma r y v e c t o r , a n e n t r y c o r r e s p o n d i n g t o a me s s a g e ( s ) h a v i n g t h e
12
s ame i d e n t i f i e r a s t h a t o f a n a l r e a d y - d e l i v e r e d me s s a g e ( s ) l i s t e d i n t h e
ACK l i s t r e c e i v e d f r om t h e a d j a c e n t DTN n o d e . As a r e s u l t , e a c h DTN
n o d e 1 d o e s n o t f o rwa r d t h e me s s a g e wh i c h h a s a l r e a d y a r r i v e d a t t h e
f i n a l d e s t i n a t i o n n o d e t o a n a d j a c e n t n o d e a n y l o n g e r . Th i s i s b e c a u s e ,
s i n c e t h e e n t r y c o r r e s p o n d i n g t o t h e me s s a g e wh i c h h a s a l r e a d y a r r i v 5 e d
a t t h e f i n a l d e s t i n a t i o n n o d e i s e l imi n a t e d f r om t h e s umma r y v e c t o r ,
t h e me s s a g e wh i c h h a s a l r e a d y a r r i v e d a t t h e f i n a l d e s t i n a t i o n n o d e i s
n o t p r e s e n t e d t o a n a d j a c e n t DTN n o d e a n y l o n g e r . Th e r e f o r e , i t i s
p o s s i b l e t o p r e v e n t c o p i e s o f t h e me s s a g e wh i c h h a s a l r e a d y a r r i v e d a t
10 t h e f i n a l d e s t i n a t i o n n o d e f r om b e i n g s p r e a d wi t h i n t h e DTN 1 0 0 .
[0031]
Fu r t h e r , e a c h DTN n o d e 1 ma y u p d a t e i t s own me s s a g e b u f f e r
b a s e d o n t h e ACK l i s t r e c e i v e d f r om t h e a d j a c e n t DTN n o d e .
S p e c i f i c a l l y, e a c h DTN n o d e 1 ma y d e l e t e , f r om i t s own me s s a g e
15 b u f f e r , a me s s a g e h a v i n g t h e s ame i d e n t i f i e r a s t h a t o f a n a l r e a d y -
d e l i v e r e d me s s a g e l i s t e d i n t h e ACK l i s t r e c e i v e d f r om t h e a d j a c e n t
DTN n o d e . No t e t h a t t h e d e l e t i o n o f a me s s a g e ma y b e p e r f o rme d b y
o v e rwr i t i n g ( u p d a t i n g ) t h e me s s a g e d a t a s t o r e d i n t h e me s s a g e b u f f e r
o f t h e DTN n o d e 1 wi t h n u l l d a t a h a v i n g a d a t a s i z e o f z e r o . I n t h i s
20 wa y, e a c h DTN n o d e 1 c a n i n c r e a s e t h e u s e e f f i c i e n c y o f t h e me s s a g e
b u f f e r , t h u s c o n t r i b u t i n g t o a n imp r o v eme n t i n t h e me s s a g e d e l i v e r y
s u c c e s s r a t e o f t h e DTN 1 0 0 . T h i s i s b e c a u s e , b y d e l e t i n g t h e
u n n e c e s s a r y me s s a g e , wh i c h d o e s n o t n e e d t o b e f o rwa r d e d a n y l o n g e r ,
f r om t h e me s s a g e b u f f e r , t h a t a r e a o f t h e me s s a g e b u f f e r c a n b e u s e d
25 f o r o t h e r me s s a g e s t h a t s h o u l d b e f o rwa r d e d .
[0032]
Ne x t , a c o n f i g u r a t i o n e x amp l e o f t h e DTN n o d e 1 a n d i t s
o p e r a t i o n a r e e x p l a i n e d h e r e i n a f t e r i n a mo r e d e t a i l e d ma n n e r . Fi g . 4
s h ows a c o n f i g u r a t i o n e x amp l e o f t h e DTN n o d e 1 . A wi r e l e s s
30 c ommu n i c a t i o n u n i t 1 1 wi r e l e s s l y c ommu n i c a t e s wi t h o t h e r DTN n o d e s
1 i n t h e DTN 1 0 0 . Th a t i s , t h e wi r e l e s s c ommu n i c a t i o n u n i t 1 1
i n c l u d e s a t r a n s c e i v e r h a v i n g t h e p h y s i c a l l a y e r s o f t h e wi r e l e s s
c ommu n i c a t i o n t e c h n o l o g y u s e d i n t h e DTN 1 0 0 , a n d s u p p o r t s t h e
p r o t o c o l s u i t e o f t h e d a t a l i n k l a y e r , t h e n e two r k l a ye r , a n d t h e
13
t r a n s p o r t l a y e r o f t h e wi r e l e s s c ommu n i c a t i o n t e c h n o l o g y u s e d i n t h e
DTN 1 0 0 . Fu r t h e r , t h e wi r e l e s s c ommu n i c a t i o n u n i t 1 1 a l s o s u p p o r t s a
b u n d l e l a y e r p r o t o c o l . Th e b u n d l e l a y e r p r o t o c o l i s p o s i t i o n e d b e twe e n
t h e a p p l i c a t i o n l a y e r a n d t h e t r a n s p o r t l a y e r , a n d p r o v i d e s s t o r e - a n d -
f o rwa r d c ommu n i c a t i o n n e c e s s a r y f o r t h e DTN. Th e P r o t o c o l Da 5 t a
Un i t ( PDU) o f t h e b u n d l e l a y e r ma y b e r e f e r r e d t o a s a me s s a g e b u n d l e
o r a d a t a b u n d l e .
[0033]
Th e r a d i o c ommu n i c a t i o n u n i t 1 1 ma n a g e s t h e a b o v e - d e s c r i b e d
10 s umma r y v e c t o r a n d t h e ACK l i s t a c c o r d i n g t o t h e b u n d l e l a y e r
p r o t o c o l . Fu r t h e r , d u r i n g c o n t a c t wi t h a n a d j a c e n t DTN n o d e , t h e
r a d i o c ommu n i c a t i o n u n i t 1 1 e x c h a n g e s t h e s umma r y v e c t o r s a n d t h e
ACK l i s t s wi t h t h e a d j a c e n t DTN n o d e , a n d s e n d s a n d / o r r e c e i v e s
me s s a g e s a c c o r d i n g t o t h e b u n d l e l a y e r p r o t o c o l .
15 [0034]
A d a t a b u f f e r 1 2 i s c o n f i g u r e d t o s t o r e a p l u r a l i t y o f me s s a g e s
t r a n s f e r r e d t h r o u g h t h e DTN 1 0 0 . Th e d a t a b u f f e r 1 2 ma y b e a v o l a t i l e
memo r y s u c h a s a Dyn ami c Ra n d om Ac c e s s Memo r y (DRAM) a n d a
S t a t i c Ra n d om Ac c e s s Memo r y ( SRAM) , a n o n v o l a t i l e memo r y s u c h a s
20 a h a r d d i s k d r i v e a n d a f l a s h memo r y , o r a c omb i n a t i o n t h e r e o f .
[0035]
A s e q u e n c e d i a g r am s h own i n Fi g . 5 s h ows a n e x amp l e o f a
c ommu n i c a t i o n p r o c e d u r e o f t h e DTN n o d e 1 a c c o r d i n g t o t h i s
e x emp l a r y emb o d ime n t . Th e e x amp l e s h own i n Fi g . 5 s h ows a c a s e
25 wh e r e two DTN n o d e s 1 ( 1A a n d 1B) mo v e c l o s e r t o e a c h o t h e r a n d
h e n c e s t a r t c o n t a c t t h e r e b e twe e n . I n s t e p s S 1 0 1 a n d S1 0 2 , t h e DTN
n o d e s 1A a n d 1B e x c h a n g e t h e i r ACK l i s t s . Th a t i s , t h e DTN n o d e 1A
s e n d s i t s ACK l i s t A t o t h e DTN n o d e 1B ( s t e p S 1 0 1 ) . Th e DTN n o d e
1B s e n d s i t s ACK l i s t B t o t h e DTN n o d e 1A ( s t e p S 1 0 2 ) . I n a s t e p
30 S 1 0 3 , t h e DTN n o d e 1A u p d a t e s i t s ACK l i s t A a n d s umma r y v e c t o r A
b a s e d o n t h e ACK l i s t B r e c e i v e d f r om t h e DTN n o d e 1B. I n a s t e p
S 1 0 4 , t h e DTN n o d e 1B u p d a t e s i t s ACK l i s t B a n d s umma r y v e c t o r B
b a s e d o n t h e ACK l i s t A. Th e u p d a t i n g p r o c e d u r e o f t h e ACK l i s t a n d
t h e s umma r y v e c t o r i s p e r f o rme d a s d e s c r i b e d a b o v e . Ea c h o f t h e DTN
14
n o d e s 1A a n d 1B ma y f u r t h e r u p d a t e i t s me s s a g e b u f f e r .
[0036]
I n s t e p s S 1 0 5 a n d S 1 0 6 , t h e DTN n o d e s 1A a n d 1B e x c h a n g e
t h e i r s umma r y v e c t o r s , wh i c h h a v e b e e n u p d a t e d b a s e d o n t h e ACK
l i s t s o f t h e c o u n t e r p a r t DTN n o d e s . Th a t i s , t h e DTN n o d e 1A s e n 5 d s
i t s s umma r y v e c t o r A, wh i c h h a s b e e n u p d a t e d b a s e d o n t h e ACK l i s t B
o f t h e c o u n t e r p a r t DTN n o d e , t o t h e DTN n o d e 1B ( s t e p S 1 0 5 ) . Th e
DTN n o d e 1B s e n d s i t s s umma r y v e c t o r B, wh i c h h a s b e e n u p d a t e d
b a s e d o n t h e ACK l i s t A o f t h e c o u n t e r p a r t DTN n o d e , t o t h e DTN n o d e
10 1A ( s t e p S 1 0 6 ) .
[0037]
I n a s t e p S 1 0 7 , t h e DTN n o d e 1A c omp a r e s i t s s umma r y v e c t o r A
wi t h t h e s umma r y v e c t o r B o f t h e c o u n t e r p a r t DTN n o d e , a n d r e q u e s t s
t h e DTN n o d e 1B t o s e n d a me s s a g e ( s ) t h a t i s n o t i n c l u d e d i n t h e
15 s umma r y v e c t o r A. I n a s t e p S 1 0 8 , t h e DTN n o d e 1B c omp a r e s i t s
s umma r y v e c t o r B wi t h t h e s umma r y v e c t o r A o f t h e c o u n t e r p a r t DTN
n o d e , a n d r e q u e s t s t h e DTN n o d e 1A t o s e n d a me s s a g e ( s ) t h a t i s n o t
i n c l u d e d i n t h e s umma r y v e c t o r B. I n a s t e p S 1 0 9 , e a c h o f t h e DTN
n o d e s 1A a n d 1B s e n d s t h e me s s a g e s r e q u e s t e d b y t h e c o u n t e r p a r t DTN
20 n o d e t o i t . Ea c h o f t h e DTN n o d e s 1A a n d 1B s t o r e s t h e me s s a g e
r e c e i v e d f r om t h e c o u n t e r p a r t DTN n o d e i n t o i t s own me s s a g e b u f f e r .
[0038]
I n s t e p s S 1 1 0 a n d S 1 1 1 , t h e DTN n o d e s 1A a n d 1B u p d a t e t h e i r
r e s p e c t i v e s umma r y v e c t o r s A a n d B b a s e d o n t h e r e s u l t o f t h e s t e p
25 S 1 0 9 .
[0039]
Ac c o r d i n g t o t h e p r o c e d u r e s h own i n Fi g . 5 , t h e s umma r y
v e c t o r s , wh i c h h a v e b e e n u p d a t e d b a s e d o n t h e ACK l i s t s o f t h e
a d j a c e n t DTN n o d e s , a r e e x c h a n g e d i n t h e s t e p s S 1 0 5 a n d S 1 0 6 .
30 Th e r e f o r e , i t p r o v i d e s a n a d v a n t a g e t h a t t h e s i z e s o f t h e s umma r y
v e c t o r c a n b e r e d u c e d a n d i n f o rma t i o n a b o u t me s s a g e s t h a t i s
u n n e c e s s a r y f o r t h e a d j a c e n t DTN n o d e i s n o t p r e s e n t e d t o t h e a d j a c e n t
DTN n o d e . Th i s i s b e c a u s e i n f o rma t i o n a b o u t me s s a g e s c o r r e s p o n d i n g
t o r e s p e c t i v e ACK me s s a g e s r e c o g n i z e d b y t h e a d j a c e n t DTN n o d e h a s
15
a l r e a d y b e e n e l imi n a t e d f r om t h e s umma r y v e c t o r t o b e e x c h a n g e d .
[0040]
Ot h e r e x amp l e s o f t h e c ommu n i c a t i o n p r o c e d u r e o f t h e DTN
n o d e 1 a r e e x p l a i n e d h e r e i n a f t e r i n t h e b e l ow - d e s c r i b e d s e c o n d a n d
t h i r d e x emp l a r y emb o d ime n t 5 s .
[0041]
S e c o n d e x emp l a r y emb o d ime n t
I n t h i s e x emp l a r y emb o d ime n t , a s p e c i f i c e x amp l e o f t h e
c ommu n i c a t i o n p r o c e d u r e o f t h e DTN n o d e 1 i s e x p l a i n e d . Th e
10 c o n f i g u r a t i o n e x amp l e o f t h e DTN 1 0 0 i n t h i s e x emp l a r y emb o d ime n t i s
s imi l a r t o t h a t s h own i n Fi g . 1 , a n d t h e c o n f i g u r a t i o n e x amp l e o f t h e
DTN n o d e 1 i s s imi l a r t o t h a t s h own i n Fi g . 4 .
[0042]
A s e q u e n c e d i a g r am s h own i n Fi g . 6 s h ows a n e x amp l e o f a
15 c ommu n i c a t i o n p r o c e d u r e o f t h e DTN n o d e 1 a c c o r d i n g t o t h i s
e x emp l a r y emb o d ime n t . Wh e n t h e p r o c e d u r e s h own i n Fi g . 6 i s
c omp a r e d wi t h t h a t s h own i n Fi g . 5 , i t i s s e e n t h a t t h e p r o c e d u r e s h own
i n Fi g . 6 i s d i f f e r e n t f r om t h a t s h own i n Fi g . 5 i n t h a t t h e s umma r y
v e c t o r t h a t h a s n o t ye t b e e n u p d a t e d b a s e d o n t h e ACK l i s t s o f t h e
20 a d j a c e n t DTN n o d e i s s e n t t o t h e a d j a c e n t DTN n o d e , a n d t h e n
me s s a g e s a r e e x c h a n g e d i n t h e p r o c e d u r e s h own i n Fi g . 6 .
[0043]
I n s t e p s S 2 0 1 a n d S 2 0 2 , t h e DTN n o d e s 1A a n d 1B e x c h a n g e
t h e i r ACK l i s t s a n d s umma r y v e c t o r s . Th a t i s , t h e DTN n o d e 1A s e n d s
25 i t s ACK l i s t A a n d s umma r y v e c t o r A t o t h e DTN n o d e 1B ( s t e p S 2 0 1 ) .
Th e DTN n o d e 1B s e n d s i t s ACK l i s t B a n d s umma r y v e c t o r B t o t h e
DTN n o d e 1A ( s t e p S 2 0 2 ) .
[0044]
I n a s t e p S 2 0 3 , t h e DTN n o d e 1A r e q u e s t s t h e DTN n o d e 1B t o
30 s e n d a me s s a g e ( s ) t h a t i s l i s t e d i n t h e s umma r y v e c t o r B o f t h e DTN
n o d e 1B b u t i s l i s t e d i n n e i t h e r i t s own s umma r y v e c t o r A n o r i t s own
ACK l i s t A. S imi l a r l y , i n a s t e p S 2 0 4 , t h e DTN n o d e 1B r e q u e s t s t h e
DTN n o d e 1A t o s e n d a me s s a g e ( s ) t h a t i s l i s t e d i n t h e s umma r y v e c t o r
A o f t h e DTN n o d e 1A b u t i s l i s t e d i n n e i t h e r i t s own s umma r y v e c t o r
16
B n o r i t s own ACK l i s t B.
[0045]
I n a s t e p S 2 0 5 , e a c h o f t h e DTN n o d e s 1A a n d 1B s e n d s t h e
me s s a g e s r e q u e s t e d b y t h e c o u n t e r p a r t DTN n o d e t o i t . Ea c h o f t h e
DTN n o d e s 1A a n d 1B s t o r e s t h e me s s a g e r e c e i v e d f r om t h e c o u n t e r p a 5 r t
DTN n o d e i n t o i t s own me s s a g e b u f f e r .
[0046]
I n a s t e p S 2 0 6 , t h e DTN n o d e 1A u p d a t e s t h e ACK l i s t A
a c c o r d i n g t o t h e ACK l i s t B r e c e i v e d i n t h e s t e p S 2 0 1 . Th e DTN n o d e
10 1A ma y o b t a i n t h e u n i o n o f t h e ACK l i s t s A a n d B. Fu r t h e r , t h e DTN
n o d e 1A u p d a t e s t h e s umma r y v e c t o r A a c c o r d i n g t o t h e ACK l i s t B
r e c e i v e d i n t h e s t e p S 2 0 1 a n d o n t h e r e s u l t o f t h e me s s a g e e x c h a n g e
p e r f o rme d i n t h e s t e p S 2 0 5 . Th e DTN n o d e 1A ma y d e l e t e t h e
i d e n t i f i e r o f a me s s a g e l i s t e d i n t h e ACK l i s t B f r om t h e s umma r y
15 v e c t o r A a n d a d d t h e i d e n t i f i e r o f a me s s a g e r e c e i v e d i n t h e s t e p S 2 0 5
t o t h e s umma r y v e c t o r A.
[0047]
I n a s t e p S 2 0 7 , s imi l a r l y t o t h e s t e p S 2 0 6 , t h e DTN n o d e 1B
u p d a t e s t h e ACK l i s t B a c c o r d i n g t o t h e ACK l i s t A r e c e i v e d i n t h e
20 s t e p S 2 0 2 . Fu r t h e r , t h e DTN n o d e 1B u p d a t e s t h e s umma r y v e c t o r B
a c c o r d i n g t o t h e ACK l i s t A r e c e i v e d i n t h e s t e p S 2 0 2 a n d t h e r e s u l t o f
t h e me s s a g e e x c h a n g e p e r f o rme d i n t h e s t e p S2 0 5 .
[0048]
No t e t h a t i n t h e s t e p s S 2 0 6 a n d S2 0 7 , e a c h o f t h e DTN n o d e s 1A
25 a n d 1B ma y f u r t h e r u p d a t e i t s me s s a g e b u f f e r .
[0049]
Th e t ime d u r i n g wh i c h a d j a c e n t DTN n o d e s 1 c a n c ommu n i c a t e
wi t h e a c h o t h e r ma y b e l imi t e d . Th e r e f o r e , i t i s d e s i r a b l e t h a t t h e t ime
r e q u i r e d f o r c omp l e t i n g a me s s a g e e x c h a n g e b e r e d u c i b l e . Th i s i s
30 b e c a u s e , b y d o i n g s o , f a i l e d me s s a g e e x c h a n g e s c a n b e r e d u c e d .
Ac c o r d i n g t o t h e p r o c e d u r e s h own i n Fi g . 6 , t h e me s s a g e s c a n b e
e x c h a n g e d wi t h o u t wa i t i n g f o r t h e c omp l e t i o n o f t h e s umma r y v e c t o r
u p d a t i n g p r o c e s s p e r f o rme d b a s e d o n t h e ACK l i s t r e c e i v e d f r om t h e
a d j a c e n t DTN n o d e ( s t e p s S 2 0 3 t o S 2 0 5 ) . Th e r e f o r e , i t i s e x p e c t e d
17
t h a t t h e p r o c e d u r e s h own i n Fi g . 6 wi l l b e a b l e t o r e d u c e t h e t ime
n e c e s s a r y f o r c omp l e t i n g a me s s a g e e x c h a n g e c omp a r e d t o t h e t ime
n e c e s s a r y i n t h e p r o c e d u r e s h own i n Fi g . 5 .
[0050]
Th i r d e x emp l a r y emb o d ime 5 n t
Th e c ommu n i c a t i o n p r o c e d u r e s o f t h e DTN n o d e 1 e x p l a i n e d
a b o v e i n t h e f i r s t a n d s e c o n d e x emp l a r y emb o d ime n t s a r e me r e l y
e x amp l e s , a n d c a n b e mo d i f i e d i n a v a r i o u s f a s h i o n s . Fo r e x amp l e , t h e
e x c h a n g e o f t h e ACK l i s t s b e twe e n a d j a c e n t DTN n o d e s 1 ma y b e
10 p e r f o rme d t h r o u g h a s e p a r a t e p r o c e d u r e f r om t h e e x c h a n g e o f t h e
s umma r y v e c t o r s a n d t h e t r a n smi s s i o n / r e c e p t i o n o f t h e me s s a g e s .
Fu r t h e r , t h e c ommu n i c a t i o n p r o c e d u r e r e g a r d i n g t h e ACK l i s t ma y
i n c l u d e o n l y o n e -wa y t r a n smi s s i o n , r a t h e r t h a n p e r f o rmi n g t h e
e x c h a n g e o f t h e ACK l i s t s ( i . e . , r a t h e r t h a n p e r f o rmi n g two -wa y
15 t r a n smi s s i o n ) .
[0051]
Fi g . 7 s h ows a s imp l e s e q u e n c e s h owi n g o n e -wa y r e c e p t i o n o f
t h e ACK l i s t B f r om t h e DTN n o d e 1B a n d u p d a t i n g o f t h e own
s umma r y v e c t o r A a n d ACK l i s t A b a s e d o n t h i s o n e -wa y r e c e p t i o n . I n
20 a s t e p S 3 0 1 , t h e DTN n o d e 1A r e c e i v e s t h e ACK l i s t B f r om t h e DTN
n o d e 1B. I n a s t e p S 3 0 2 , t h e DTN n o d e 1A u p d a t e s i t s own ACK l i s t A
a n d s umma r y v e c t o r A b a s e d o n t h e ACK l i s t B r e c e i v e d f r om t h e DTN
n o d e 1B.
[0052]
25 S p e c i f i c a l l y, t h e DTN n o d e 1A ma y e l imi n a t e , f r om i t s own
s umma r y v e c t o r A, a me s s a g e h a v i n g t h e s ame i d e n t i f i e r a s t h a t o f a n
a l r e a d y - d e l i v e r e d me s s a g e l i s t e d i n t h e ACK l i s t B o f t h e a d j a c e n t
DTN n o d e 1B. As a r e s u l t , t h e DTN n o d e 1A d o e s n o t f o rwa r d t h e
me s s a g e wh i c h h a s a l r e a d y a r r i v e d a t t h e f i n a l d e s t i n a t i o n n o d e t o
30 a d j a c e n t nodes a n y l o n g e r . Th i s i s b e c a u s e , s i n c e t h e me s s a g e wh i c h
h a s a l r e a d y a r r i v e d a t t h e f i n a l d e s t i n a t i o n n o d e i s e l imi n a t e d f r om t h e
s umma r y v e c t o r A, t h e DTN n o d e 1A d o e s n o t p r e s e n t t h e me s s a g e ,
wh i c h h a s a l r e a d y a r r i v e d a t t h e f i n a l d e s t i n a t i o n n o d e , t o a d j a c e n t
DTN n o d e s a n y l o n g e r . Th e r e f o r e , i t i s p o s s i b l e t o p r e v e n t c o p i e s o f
18
t h e me s s a g e wh i c h h a s a l r e a d y a r r i v e d a t t h e f i n a l d e s t i n a t i o n n o d e
f r om b e i n g s p r e a d wi t h i n t h e DTN 1 0 0 .
[0053]
Fo u r t h e x emp l a r y emb o d ime n t
I n t h i s e x emp l a r y emb o d ime n t , a mo d i f i e d e x amp l e o f t h e d a 5 t a
s t r u c t u r e o f t h e s umma r y v e c t o r a n d t h e ACK l i s t i s e x p l a i n e d .
S p e c i f i c a l l y, a n e x amp l e i n wh i c h t h e ACK l i s t i s c omb i n e d wi t h t h e
s umma r y v e c t o r i s s h own i n t h i s e x emp l a r y emb o d ime n t . Th a t i s , i n
t h i s e x emp l a r y emb o d ime n t , t h e ACK l i s t i s p i g g y b a c k e d on t h e
10 s umma r y v e c t o r . I n o t h e r wo r d s , i n t h i s e x emp l a r y emb o d ime n t , t h e
s umma r y v e c t o r a n d t h e ACK l i s t a r e ma n a g e d a s a c ommo n l i s t i n a
DTN n o d e . S p e c i f i c a l l y , i n t h i s e x emp l a r y emb o d ime n t , e a c h e n t r y i n
t h e s umma r y v e c t o r i n c l u d e s i n f o rma t i o n f o r i n d i c a t i n g wh e t h e r t h a t
e n t r y i s f o r a me s s a g e s t o r e d i n t h e me s s a g e b u f f e r o r f o r a n ACK
15 me s s a g e . Th i s i n f o rma t i o n ma y b e , f o r e x amp l e , a n ACK f l a g
i n d i c a t i n g wh e t h e r i t i s a n ACK me s s a g e o r n o t . Al t e r n a t i v e l y , t h i s
i n f o rma t i o n ma y i n d i c a t e wh e t h e r t h e e n t r y i n t h e s umma r y v e c t o r i s
a s s o c i a t e d wi t h v a l i d d a t a o r n o t . I n t h i s c a s e , wh e n a n e n t r y i n t h e
s umma r y v e c t o r i s a s s o c i a t e d wi t h i n v a l i d d a t a ( e . g . , n u l l d a t a h a v i n g a
20 d a t a s i z e o f z e r o ) , t h a t e n t r y ma y b e r e g a r d e d a s a n e n t r y f o r a n ACK
me s s a g e .
[0054]
Fi g . 8 s h ows a n e x amp l e o f a s umma r y v e c t o r c o n t a i n i n g a n ACK
a c c o r d i n g t o t h i s e x emp l a r y emb o d ime n t . A s umma r y v e c t o r 4 0 s h own
25 i n Fi g . 8 i n c l u d e s a n o d e ID f i e l d 2 0 0 , L n umb e r o f me s s a g e ID f i e l d s
4 0 1 , a n d L n umb e r o f ACK f l a g f i e l d s 4 0 2 . Th e L ACK f l a g f i e l d s 4 0 2
c o r r e s p o n d t o t h e L me s s a g e ID f i e l d s 4 0 1 . Ea c h ACK f l a g f i e l d 4 0 2
i n d i c a t e s wh e t h e r t h e v a l u e o f t h e c o r r e s p o n d i n g me s s a g e ID f i e l d 4 0 1
i s f o r a me s s a g e s t o r e d i n t h e me s s a g e b u f f e r o r f o r a n ACK me s s a g e .
30 Fo r e x amp l e , wh e n t h e v a l u e o f a n ACK f l a g f i e l d 4 0 2 i s " 0 " , t h e v a l u e
o f i t s c o r r e s p o n d i n g me s s a g e ID f i e l d 4 0 1 i s c o n s i d e r e d t o b e t h e ID o f
a me s s a g e s t o r e d i n t h e me s s a g e b u f f e r . On t h e o t h e r h a n d , wh e n t h e
v a l u e o f a n ACK f l a g f i e l d 4 0 2 i s " 1 " , t h e v a l u e o f i t s c o r r e s p o n d i n g
me s s a g e ID f i e l d 4 0 1 i s c o n s i d e r e d t o b e t h e ID o f a n ACK me s s a g e ,
19
i . e . , t h e ID o f a me s s a g e wh i c h h a s a l r e a d y a r r i v e d a t t h e f i n a l
d e s t i n a t i o n n o d e .
[0055]
Fi g . 9 s h ows a n o t h e r e x amp l e o f a s umma r y v e c t o r c o n t a i n i n g a n
ACK a c c o r d i n g t o t h i s e x emp l a r y emb o d ime n t . A s umma r y v e c t o r 4 5 1
s h own i n Fi g . 9 i n c l u d e s a n o d e ID f i e l d 2 0 0 , L n umb e r o f me s s a g e ID
f i e l d s 4 0 1 , a n d L n umb e r o f d a t a s i z e f i e l d s 4 0 3 . Th e L d a t a s i z e
f i e l d s 4 0 3 c o r r e s p o n d t o t h e L me s s a g e ID f i e l d s 4 0 1 . Ea c h d a t a s i z e
f i e l d 4 0 3 i n d i c a t e s wh e t h e r t h e v a l u e o f t h e c o r r e s p o n d i n g me s s a g e ID
10 f i e l d 4 0 1 i s f o r a me s s a g e s t o r e d i n t h e me s s a g e b u f f e r o r f o r a n ACK
me s s a g e . S p e c i f i c a l l y, wh e n a d a t a s i z e f i e l d 4 0 3 h a s a v a l i d v a l u e ( a
v a l i d d a t a s i z e l a r g e r t h a n z e r o ) , i t i n d i c a t e s t h a t t h e e n t r y i s f o r a
me s s a g e s t o r e d i n t h e me s s a g e b u f f e r . On t h e o t h e r h a n d , wh e n a d a t a
s i z e f i e l d 4 0 3 h a s a v a l u e " z e r o " o r a n i n v a l i d v a l u e , i t i n d i c a t e s t h a t
15 t h e e n t r y i s f o r a n ACK me s s a g e .
[0056]
By c omb i n i n g t h e ACK l i s t wi t h t h e s umma r y v e c t o r , t h a t i s , b y
u s i n g an ACK me s s a g e ( s ) a d d e d i n ( p i g g y b a c k e d on) t h e s umma r y
v e c t o r , t h e p r o c e s s f o r e x c h a n g i n g ACK l i s t s b e c ome s u n n e c e s s a r y i n
20 t h e c ommu n i c a t i o n p r o c e d u r e b e twe e n a d j a c e n t DTN n o d e s . Th e r e f o r e ,
o n l y t h e e x c h a n g e o f s umma r y v e c t o r s n e e d t o b e p e r f o rme d . I n o t h e r
wo r d s , t h e DTN n o d e 1 c a n s p r e a d ACK me s s a g e s ( i . e . , n o t i c e
i n d i c a t i n g me s s a g e s t h a t have a r r i v e d a t t h e i r f i n a l d e s t i n a t i o n ) b y
u s i n g t h e me c h a n i sm f o r s p r e a d i n g me s s a g e s i n a c c o r d a n c e wi t h t h e
25 Ep i d emi c r o u t i n g o r t h e l i k e , wh i c h u s e s a s umma r y v e c t o r . Th e r e f o r e ,
t h e DTN n o d e 1 d o e s n o t r e q u i r e a n y a d d i t i o n a l me c h a n i sm f o r
s p r e a d i n g ACK me s s a g e s ( i . e . , a p r o c e d u r e f o r e x c h a n g i n g ACK l i s t s ) .
Ac c o r d i n g l y, t h e c ommu n i c a t i o n p r o c e d u r e b e twe e n a d j a c e n t DTN
n o d e s 1 c a n b e s imp l i f i e d .
30 [0057]
S p e c i f i c a l l y, t h e DTN n o d e 1 ma y o p e r a t e a s d e s c r i b e d b e l ow.
Wh e n a s umma r y v e c t o r r e c e i v e d f r om a n a d j a c e n t DTN n o d e i n c l u d e s
a n e n t r y h a v i n g t h e s ame me s s a g e ID a s t h a t o f a n e n t r y i n c l u d e d i n i t s
own s umma r y v e c t o r , a n d wh i l e t h e d a t a s i z e i n d i c a t e d i n t h e i t s own
20
s umma r y v e c t o r h a s a v a l i d v a l u e , t h e d a t a s i z e i n d i c a t e d i n t h e
s umma r y v e c t o r o f t h e a d j a c e n t DTN n o d e h a s z e r o o r a n i n v a l i d v a l u e ,
t h e DTN n o d e 1 d e l e t e s t h e me s s a g e d a t a s t o r e d i n t h e d a t a b u f f e r 1 2 .
Fu r t h e r , t h e DTN n o d e 1 o v e rwr i t e s ( u p d a t e s ) t h e d a t a s i z e f i e l d 4 0 3 o f
t h a t d a t a i n i t s own s umma r y v e c t o r wi t h z e r o o r a n i n v a l i d v a l u e . B5 y
t h e a b o v e - d e s c r i b e d me s s a g e u p d a t i n g o p e r a t i o n , i t i s p o s s i b l e t o
s p r e a d a n ACK me s s a g e a n d d e l e t e a n a l r e a d y - d e l i v e r e d me s s a g e f r om
t h e d a t a b u f f e r 1 2 .
[0058]
10 Fu r t h e r , t h e u s e o f t h e me c h a n i sm f o r u p d a t i n g a me s s a g e
( u p d a t i n g a me s s a g e wi t h n u l l d a t a ) a l s o p r o v i d e s a n a d v a n t a g e t h a t t h e
DTN n o d e 1 c a n u p d a t e o r r e s e t t h e e x p i r a t i o n t ime ( e . g . , a l i f e s p a n
b a s e d o n a t ime s t amp , a Time -To- Li v e (TTL) v a l u e , o r a Time s -To-
S e n d (TTS ) v a l u e ) o f t h e me s s a g e . Th e r e f o r e , i t i s p o s s i b l e t o p r e v e n t
15 a s i t u a t i o n i n wh i c h a n e n t r y i n t h e s umma r y v e c t o r i n d i c a t i n g t h a t t h e
d a t a s i z e i s z e r o o r a n i n v a l i d v a l u e ( i . e . , a n e n t r y c o r r e s p o n d i n g t o a n
ACK me s s a g e ) i s d e l e t e d b e f o r e t h e e n t r y i s s u f f i c i e n t l y s p r e a d wi t h i n
t h e DTN 1 0 0 d u e t o t h e e x p i r a t i o n o f t h e e x p i r a t i o n t ime . As a r e s u l t ,
i t i s p o s s i b l e t o f a c i l i t a t e a s i t u a t i o n i n wh i c h a n ACK me s s a g e i s
20 s u f f i c i e n t l y s p r e a d wi t h i n t h e DTN 1 0 0 a n d a n a l r e a d y - d e l i v e r e d
me s s a g e wh i c h h a s a l r e a d y b e e n d e l i v e r e d t o i t s f i n a l d e s t i n a t i o n n o d e
i s d e l e t e d f r om t h e DTN 1 0 0 .
[0059]
As s h own i n Fi g . 9 , t h e u s e o f t h e d a t a s i z e i n f o rma t i o n i n t h e
25 s umma r y v e c t o r f o r i n d i c a t i n g wh e t h e r t h e e n t r y i s f o r a n ACK o r n o t
i s p a r t i c u l a r l y e f f e c t i v e wh e n t h e d a t a s i z e i n f o rma t i o n i s i n c l u d e d i n
t h e s umma r y v e c t o r . Th e d a t a s i z e i n f o rma t i o n i n c l u d e d i n t h e
s umma r y v e c t o r c a n b e u s e d a s a p a r t o f t h e i d e n t i f i e r o f t h e me s s a g e
o r f o r i n d i c a t i n g wh e t h e r t h e me s s a g e i s u p d a t e d o r n o t . Fu r t h e r , i n
30 t h e e x amp l e s h own i n Fi g . 9 , s i n c e t h e d a t a s i z e i n f o rma t i o n i s u s e d t o
i n d i c a t e wh e t h e r t h e e n t r y i s f o r a n ACK o r n o t , i t h a s a n a d v a n t a g e
t h a t t h e r e i s n o n e e d t o i n t r o d u c e a n ew s umma r y v e c t o r s t r u c t u r e s u c h
a s a s t r u c t u r e i n c l u d i n g a n AC K f l a g f i e l d s h own i n Fi g . 8 .
[0060]
21
Ot h e r e x emp l a r y emb o d ime n t s
Th e c ommu n i c a t i o n p r o c e d u r e p e r f o rme d b y t h e DTN n o d e 1
e x p l a i n e d i n t h e a b o v e - d e s c r i b e d p l u r a l i t y o f e x emp l a r y emb o d ime n t s
ma y b e imp l eme n t e d b y c a u s i n g a c omp u t e r s ys t em t o e x e c u t e a
p r o g r am. S p e c i f i c a l l y, o n e o r mo r e p r o g r ams i n c l u d i n g i n s t r u c t i o 5 n s
f o r c a u s i n g a c omp u t e r s ys t em t o p e r f o rm t h e a l g o r i sm e x p l a i n e d i n t h e
s p e c i f i c a t i o n o f t h e p r e s e n t a p p l i c a t i o n wi t h r e f e r e n c e t o t h e s e q u e n c e
d i a g r ams o r t h e l i k e ma y b e c r e a t e d , a n d t h e c r e a t e d p r o g r am ma y b e
s u p p l i e d t o t h e c omp u t e r s ys t em.
10 [0061]
Th i s p r o g r am c a n b e s t o r e d i n v a r i o u s t y p e s o f n o n - t r a n s i t o r y
c omp u t e r r e a d a b l e me d i a a n d t h e r e b y s u p p l i e d t o c omp u t e r s . Th e n o n -
t r a n s i t o r y c omp u t e r r e a d a b l e me d i a i n c l u d e s v a r i o u s t y p e s o f t a n g i b l e
s t o r a g e me d i a . Ex amp l e s o f t h e n o n - t r a n s i t o r y c omp u t e r r e a d a b l e
15 me d i a i n c l u d e a ma g n e t i c r e c o r d i n g me d i um ( e . g . a f l e x i b l e d i s k , a
ma g n e t i c t a p e , a n d a h a r d d i s k d r i v e ) , a ma g n e t o - o p t i c r e c o r d i n g
me d i um ( e . g . a ma g n e t o - o p t i c d i s k ) , a Comp a c t Di s c Re a d On l y
Memo r y (CD-ROM) , a CD-R, a n d a CD-R/W, a n d a s emi c o n d u c t o r
memo r y ( e . g . a ma s k ROM, a P r o g r amma b l e ROM ( PROM) , a n
20 Er a s a b l e PROM (EPROM) , a f l a s h ROM, a n d a Ra n d om Ac c e s s Memo r y
(RAM) ) . Fu r t h e r , t h e p r o g r am c a n b e s u p p l i e d t o c omp u t e r s b y u s i n g
v a r i o u s t yp e s o f t r a n s i t o r y c omp u t e r r e a d a b l e me d i a . Ex amp l e s o f t h e
t r a n s i t o r y c omp u t e r r e a d a b l e me d i a i n c l u d e a n e l e c t r i c a l s i g n a l , a n
o p t i c a l s i g n a l , a n d a n e l e c t r oma g n e t i c wa v e . Th e t r a n s i t o r y c omp u t e r
25 r e a d a b l e me d i a c a n b e u s e d t o s u p p l y p r o g r ams t o c omp u t e r t h r o u g h a
wi r e c ommu n i c a t i o n p a t h s u c h a s a n e l e c t r i c a l wi r e a n d a n o p t i c a l f i b e r ,
o r wi r e l e s s c ommu n i c a t i o n p a t h .
[0062]
Fu r t h e r , t h e a b o v e - d e s c r i b e d e x emp l a r y emb o d ime n t s a r e me r e
30 e x amp l e s f o r t h e a p p l i c a t i o n o f t h e t e c h n i c a l i d e a a c h i e v e d b y t h e
i n v e n t o r s o f t h e p r e s e n t a p p l i c a t i o n . Th a t i s , n e e d l e s s t o s a y , t h a t
t e c h n i c a l i d e a i s n o t l imi t e d t o t h e a b o v e - d e s c r i b e d e x emp l a r y
emb o d ime n t s a n d v a r i o u s mo d i f i c a t i o n s c a n b e ma d e t h e r e t o .
[ 0 0 6 3 ]
22
Th i s a p p l i c a t i o n i s b a s e d u p o n a n d c l a ims t h e b e n e f i t o f p r i o r i t y
f r om J a p a n e s e P a t e n t Ap p l i c a t i o n No . 2 0 1 4 - 0 4 1 4 7 4 , f i l e d o n Ma r c h 4 ,
2 0 1 4 , a n d t h e d i s c l o s u r e o f wh i c h i s i n c o r p o r a t e d h e r e i n i n i t s e n t i r e t y
b y r e f e r e n c e .
Re f e r en c e S i g n s Li 5 s t
[ 0 0 6 4 ]
1 DISRUPTION/DE LAY/DISCONNECT TOLERANT NETWORK
(DTN) NODE
11 WIRE LE S S COMMUNICATION UNIT
10 12 DATA BUF FER
20 SUMMARY VECTOR
30 ACK LI ST
40 SUMMARY VECTOR CONTAINING ACK
1 0 0 DISRUPTION/DE LAY/DISCONNECT TOLERANT NETWORK
15 (DTN)
23
WE CLAIM:
1 . A n o d e d e v i c e u s e d i n a Di s r u p t i o n /De l a y/Di s c o n n e c t To l e r a n t
Ne two r k (DTN) , t h e n o d e d e v i c e c omp r i s i n g :
a c ommu n i c a t i o n u n i t c o n f i g u r e d t o c ommu n i c a t e wi t h a 5 n
a d j a c e n t n o d e i n t h e DTN; a n d
a f i r s t me s s a g e b u f f e r c o n f i g u r e d t o s t o r e a p l u r a l i t y o f
me s s a g e s t r a n s f e r r e d t h r o u g h t h e DTN, wh e r e i n
t h e c ommu n i c a t i o n u n i t i s c o n f i g u r e d t o ma n a g e a f i r s t s umma r y
10 v e c t o r a n d a n ACK l i s t , a n d a l s o c o n f i g u r e d t o r e c e i v e a s e c o n d ACK
l i s t ma n a g e d b y t h e a d j a c e n t n o d e d u r i n g c o n t a c t wi t h t h e a d j a c e n t
n o d e a n d u p d a t e t h e f i r s t ACK l i s t a n d t h e f i r s t s umma r y v e c t o r b a s e d
o n t h e s e c o n d ACK l i s t ,
t h e f i r s t s umma r y v e c t o r i n d i c a t e s o n e o r mo r e s t o r e d me s s a g e s
15 t h a t h a v e b e e n s t o r e d i n t h e f i r s t me s s a g e b u f f e r , a n d t h e f i r s t s umma r y
v e c t o r i s s e n t t o t h e a d j a c e n t n o d e , d u r i n g t h e c o n t a c t wi t h t h e
a d j a c e n t n o d e , p r i o r t o t r a n smi s s i o n o f t h e o n e o r mo r e s t o r e d
me s s a g e s ,
t h e f i r s t ACK l i s t i n d i c a t e s o n e o r mo r e ACK me s s a g e s t h a t h a v e
20 b e e n r e c o g n i z e d b y t h e n o d e d e v i c e ,
t h e s e c o n d ACK l i s t i n d i c a t e s o n e o r mo r e ACK me s s a g e s t h a t
h a v e b e e n r e c o g n i z e d b y t h e a d j a c e n t n o d e , a n d
e a c h o f t h e o n e o r mo r e ACK me s s a g e s i n d i c a t e s a n a l r e a d y -
d e l i v e r e d me s s a g e t h a t h a s a l r e a d y b e e n d e l i v e r e d t o a f i n a l d e s t i n a t i o n
25 n o d e t h r o u g h t h e DTN.
2 . Th e n o d e d e v i c e a c c o r d i n g t o Cl a im 1 , wh e r e i n
t h e c ommu n i c a t i o n u n i t r e c e i v e s t h e s e c o n d ACK l i s t wi t h a
s e c o n d s umma r y v e c t o r ma n a g e d b y t h e a d j a c e n t n o d e d u r i n g t h e
30 c o n t a c t wi t h t h e a d j a c e n t n o d e ,
t h e s e c o n d s umma r y v e c t o r i n d i c a t e s o n e o r mo r e s t o r e d
me s s a g e s t h a t h a v e b e e n s t o r e d i n a s e c o n d me s s a g e b u f f e r a r r a n g e d i n
t h e a d j a c e n t n o d e , a n d
t h e c ommu n i c a t i o n u n i t u p d a t e s t h e f i r s t ACK l i s t a n d t h e f i r s t
24
s umma r y v e c t o r a f t e r r e c e i v i n g t h e s e c o n d s umma r y v e c t o r .
3 . Th e n o d e d e v i c e a c c o r d i n g t o Cl a im 2 , wh e r e i n t h e
c ommu n i c a t i o n u n i t r e q u e s t s t h e a d j a c e n t n o d e t o s e n d a me s s a g e t h a t
i s l i s t e d i n t h e s e c o n d s umma r y v e c t o r a n d i s l i s t e d i n n e i t h e r t h e f i r 5 s t
ACK l i s t n o r t h e f i r s t s umma r y v e c t o r .
4 . Th e n o d e d e v i c e a c c o r d i n g t o Cl a im 1 , wh e r e i n a f t e r r e c e i v i n g
t h e s e c o n d ACK l i s t a n d u p d a t i n g t h e f i r s t s umma r y v e c t o r , t h e
10 c ommu n i c a t i o n u n i t s e n d s t h e u p d a t e d f i r s t s umma r y v e c t o r t o t h e
a d j a c e n t n o d e d u r i n g t h e c o n t a c t wi t h t h e a d j a c e n t n o d e .
5 . Th e n o d e d e v i c e a c c o r d i n g t o a n y o n e o f Cl a ims 1 t o 3 ,
wh e r e i n t h e f i r s t ACK l i s t i s p i g g y b a c k e d on t h e f i r s t s umma r y v e c t o r .
15
6 . Th e n o d e d e v i c e a c c o r d i n g t o a n y o n e o f Cl a ims 1 t o 3 ,
wh e r e i n t h e f i r s t s umma r y v e c t o r a n d t h e f i r s t ACK l i s t a r e ma n a g e d a s
a f i r s t c ommo n l i s t i n t h e n o d e d e v i c e .
20 7 . Th e n o d e d e v i c e a c c o r d i n g t o Cl a im 6 , wh e r e i n e a c h e n t r y i n
t h e f i r s t c ommo n l i s t i n c l u d e s i n f o rma t i o n f o r i n d i c a t i n g wh e t h e r t h e
e n t r y i s f o r a me s s a g e s t o r e d i n t h e f i r s t me s s a g e b u f f e r o r f o r a n ACK
me s s a g e .
25 8 . Th e n o d e d e v i c e a c c o r d i n g t o Cl a im 7 , wh e r e i n t h e
i n f o rma t i o n i n c l u d e s a n ACK f l a g .
9 . Th e n o d e d e v i c e a c c o r d i n g t o Cl a im 7 , wh e r e i n
t h e i n f o rma t i o n i n c l u d e s d a t a s i z e i n f o rma t i o n i n d i c a t i n g a d a t a
30 s i z e o f a me s s a g e ,
wh e n t h e d a t a s i z e i n f o rma t i o n i n d i c a t e s a v a l i d v a l u e , t h e e n t r y
c o r r e s p o n d i n g t h e r e t o i s f o r a me s s a g e s t o r e d i n t h e f i r s t me s s a g e
b u f f e r , a n d
wh e n t h e d a t a s i z e i n f o rma t i o n i n d i c a t e s z e r o o r a n i n v a l i d v a l u e ,
25
t h e e n t r y c o r r e s p o n d i n g t h e r e t o i s f o r a n ACK me s s a g e .
1 0 . Th e n o d e d e v i c e a c c o r d i n g t o Cl a im 9 , wh e r e i n
t h e s e c o n d s umma r y v e c t o r a n d t h e s e c o n d ACK l i s t ma n a g e d b y
t h e a d j a c e n t n o d e a r e d e f i n e d a s a s e c o n d c ommo n l i s 5 t ,
e a c h e n t r y i n t h e s e c o n d c ommo n l i s t i n c l u d e s d a t a s i z e
i n f o rma t i o n i n d i c a t i n g a d a t a s i z e o f a me s s a g e ,
wh e n t h e d a t a s i z e i n f o rma t i o n i n t h e s e c o n d c ommo n l i s t
i n d i c a t e s a v a l i d v a l u e , t h e e n t r y c o r r e s p o n d i n g t h e r e t o i s f o r a
10 me s s a g e s t o r e d i n a s e c o n d me s s a g e b u f f e r a r r a n g e d i n t h e a d j a c e n t
n o d e ,
wh e n t h e d a t a s i z e i n f o rma t i o n i n t h e s e c o n d c ommo n l i s t
i n d i c a t e s z e r o o r a n i n v a l i d v a l u e , t h e e n t r y c o r r e s p o n d i n g t h e r e t o i s
f o r a n ACK me s s a g e , a n d
15 t h e c ommu n i c a t i o n u n i t d e l e t e s , f r om t h e f i r s t me s s a g e b u f f e r , a
me s s a g e wh o s e d a t a s i z e i s i n d i c a t e d as z e r o o r a n i n v a l i d v a l u e i n t h e
s e c o n d c ommo n l i s t r e c e i v e d f r om t h e a d j a c e n t n o d e .
1 1 . Th e n o d e d e v i c e a c c o r d i n g t o a n y o n e o f Cl a ims 1 t o 1 0 ,
20 wh e r e i n i n r e s p o n s e t o r e c e i v i n g , t h r o u g h t h e DTN, a f i r s t me s s a g e i n
wh i c h t h e n o d e d e v i c e i s d e s i g n a t e d a s a f i n a l d e s t i n a t i o n , t h e
c ommu n i c a t i o n u n i t a d d s a n ACK me s s a g e c o r r e s p o n d i n g t o t h e f i r s t
me s s a g e i n t h e f i r s t ACK l i s t .
25 1 2 . Th e n o d e d e v i c e a c c o r d i n g t o a n y o n e o f Cl a ims 1 t o 1 1 ,
wh e r e i n t h e c ommu n i c a t i o n u n i t s e n d s t h e f i r s t ACK l i s t t o t h e
a d j a c e n t n o d e d u r i n g t h e c o n t a c t wi t h t h e a d j a c e n t n o d e .
1 3 . Th e n o d e d e v i c e a c c o r d i n g t o a n y o n e o f Cl a ims 1 t o 1 2 ,
30 wh e r e i n t h e u p d a t i n g o f t h e f i r s t ACK l i s t i s p e r f o rme d b y me r g i n g t h e
f i r s t ACK l i s t wi t h t h e s e c o n d ACK l i s t r e c e i v e d f r om t h e a d j a c e n t
n o d e .
1 4 . Th e n o d e d e v i c e a c c o r d i n g t o a n y o n e o f Cl a ims 1 t o 1 3 ,
26
wh e r e i n t h e u p d a t i n g o f t h e f i r s t s umma r y v e c t o r i s p e r f o rme d b y
e l imi n a t i n g , f r om t h e f i r s t s umma r y v e c t o r , a n e n t r y r e g a r d i n g a
me s s a g e h a v i n g t h e s ame i d e n t i f i e r a s t h a t o f t h e a l r e a d y - d e l i v e r e d
me s s a g e l i s t e d i n t h e s e c o n d ACK l i s t .
5
1 5 . Th e n o d e d e v i c e a c c o r d i n g t o a n y o n e o f Cl a ims 1 t o 1 4 ,
wh e r e i n t h e c ommu n i c a t i o n u n i t u p d a t e s t h e f i r s t me s s a g e b u f f e r b a s e d
o n t h e s e c o n d ACK l i s t .
10 1 6 . Th e n o d e d e v i c e a c c o r d i n g t o Cl a im 1 5 , wh e r e i n t h e u p d a t i n g
o f t h e f i r s t me s s a g e b u f f e r i s p e r f o rme d b y d e l e t i n g , f r om t h e f i r s t
me s s a g e b u f f e r , a me s s a g e h a v i n g t h e s ame i d e n t i f i e r a s t h a t o f t h e
a l r e a d y - d e l i v e r e d me s s a g e l i s t e d i n t h e s e c o n d ACK l i s t .
15 1 7 . Th e n o d e d e v i c e a c c o r d i n g t o a n y o n e o f Cl a ims 1 t o 1 6 ,
wh e r e i n e a c h o f t h e o n e o r mo r e ACK me s s a g e s i s g e n e r a t e d b y t h e
d e s t i n a t i o n n o d e .
1 8 . A c ommu n i c a t i o n me t h o d p e r f o rme d b y a n o d e d e v i c e u s e d i n
20 a Di s r u p t i o n /De l a y /Di s c o n n e c t To l e r a n t Ne two r k (DTN) , t h e me t h o d
c omp r i s i n g :
r e c e i v i n g a s e c o n d ACK l i s t ma n a g e d b y a n a d j a c e n t n o d e d u r i n g
c o n t a c t wi t h t h e a d j a c e n t n o d e ; a n d
u p d a t i n g a f i r s t ACK l i s t a n d a f i r s t s umma r y v e c t o r b a s e d o n
25 t h e s e c o n d ACK l i s t , t h e f i r s t ACK l i s t a n d t h e f i r s t s umma r y v e c t o r
b e i n g ma n a g e d b y t h e n o d e d e v i c e , w h e r e i n
t h e f i r s t s umma r y v e c t o r i n d i c a t e s o n e o r mo r e s t o r e d me s s a g e s
t h a t h a v e b e e n s t o r e d i n t h e f i r s t me s s a g e b u f f e r a r r a n g e d i n t h e n o d e
d e v i c e , a n d t h e f i r s t s umma r y v e c t o r i s s e n t t o t h e a d j a c e n t n o d e ,
30 d u r i n g t h e c o n t a c t wi t h t h e a d j a c e n t n o d e , p r i o r t o t r a n smi s s i o n o f t h e
o n e o r mo r e s t o r e d me s s a g e s ,
t h e f i r s t ACK l i s t i n d i c a t e s o n e o r mo r e ACK me s s a g e s t h a t h a v e
b e e n r e c o g n i z e d b y t h e n o d e d e v i c e ,
t h e s e c o n d ACK l i s t i n d i c a t e s o n e o r mo r e ACK me s s a g e s t h a t
27
h a v e b e e n r e c o g n i z e d b y t h e a d j a c e n t n o d e , a n d
e a c h o f t h e o n e o r mo r e ACK me s s a g e s i n d i c a t e s a n a l r e a d y -
d e l i v e r e d me s s a g e t h a t h a s a l r e a d y b e e n d e l i v e r e d t o a f i n a l d e s t i n a t i o n
n o d e t h r o u g h t h e DTN.
5
1 9 . Th e c ommu n i c a t i o n me t h o d a c c o r d i n g t o Cl a im 1 8 , wh e r e i n
t h e r e c e i v i n g t h e s e c o n d ACK l i s t c omp r i s e s r e c e i v i n g t h e
s e c o n d ACK l i s t wi t h a s e c o n d s umma r y v e c t o r ma n a g e d b y t h e
a d j a c e n t n o d e d u r i n g t h e c o n t a c t wi t h t h e a d j a c e n t n o d e ,
10 t h e s e c o n d s umma r y v e c t o r i n d i c a t e s o n e o r mo r e s t o r e d
me s s a g e s t h a t h a v e b e e n s t o r e d i n a s e c o n d me s s a g e b u f f e r a r r a n g e d i n
t h e a d j a c e n t n o d e , a n d
t h e u p d a t i n g t h e f i r s t ACK l i s t a n d t h e f i r s t s umma r y v e c t o r a r e
p e r f o rme d a f t e r t h e s e c o n d s umma r y v e c t o r i s r e c e i v e d .
15
2 0 . Th e c ommu n i c a t i o n me t h o d a c c o r d i n g t o Cl a im 1 9 , f u r t h e r
c omp r i s i n g r e q u e s t i n g t h e a d j a c e n t n o d e t o s e n d a me s s a g e t h a t i s
l i s t e d i n t h e s e c o n d s umma r y v e c t o r a n d i s l i s t e d i n n e i t h e r t h e f i r s t
ACK l i s t n o r t h e f i r s t s umma r y v e c t o r .
20
2 1 . Th e c ommu n i c a t i o n me t h o d a c c o r d i n g t o Cl a im 1 8 , f u r t h e r
c omp r i s i n g , a f t e r t h e r e c e i v i n g t h e s e c o n d ACK l i s t a n d t h e u p d a t i n g
t h e f i r s t s umma r y v e c t o r , s e n d i n g t h e u p d a t e d f i r s t s umma r y v e c t o r t o
t h e a d j a c e n t n o d e d u r i n g t h e c o n t a c t wi t h t h e a d j a c e n t n o d e .
25
2 2 . Th e c ommu n i c a t i o n me t h o d a c c o r d i n g t o a n y o n e o f Cl a ims
1 8 t o 2 0 , wh e r e i n t h e f i r s t ACK l i s t i s p i g g y b a c k e d on t h e f i r s t
s umma r y v e c t o r .
30 2 3 . Th e c ommu n i c a t i o n me t h o d a c c o r d i n g t o a n y o n e o f Cl a ims
1 8 t o 2 0 , wh e r e i n t h e f i r s t s umma r y v e c t o r a n d t h e f i r s t ACK l i s t a r e
ma n a g e d a s a f i r s t c ommo n l i s t i n t h e n o d e d e v i c e .
2 4 . Th e c ommu n i c a t i o n me t h o d a c c o r d i n g t o Cl a im 2 3 , wh e r e i n
28
e a c h e n t r y i n t h e f i r s t c ommo n l i s t i n c l u d e s i n f o rma t i o n f o r i n d i c a t i n g
wh e t h e r t h e e n t r y i s f o r a me s s a g e s t o r e d i n t h e f i r s t me s s a g e b u f f e r o r
f o r a n ACK me s s a g e .
2 5 . Th e c ommu n i c a t i o n me t h o d a c c o r d i n g t o Cl a im 2 4 , wh e r e 5 i n
t h e i n f o rma t i o n i n c l u d e s a n ACK f l a g .
2 6 . Th e c ommu n i c a t i o n me t h o d a c c o r d i n g t o Cl a im 2 4 , wh e r e i n
t h e i n f o rma t i o n i n c l u d e s d a t a s i z e i n f o rma t i o n i n d i c a t i n g a d a t a
10 s i z e o f a me s s a g e ,
wh e n t h e d a t a s i z e i n f o rma t i o n i n d i c a t e s a v a l i d v a l u e , t h e e n t r y
c o r r e s p o n d i n g t h e r e t o i s f o r a me s s a g e s t o r e d i n t h e f i r s t me s s a g e
b u f f e r , a n d
wh e n t h e d a t a s i z e i n f o rma t i o n i n d i c a t e s z e r o o r a n i n v a l i d v a l u e ,
15 t h e e n t r y c o r r e s p o n d i n g t h e r e t o i s f o r a n ACK me s s a g e .
2 7 . Th e c ommu n i c a t i o n me t h o d a c c o r d i n g t o Cl a im 2 6 , wh e r e i n
t h e s e c o n d s umma r y v e c t o r a n d t h e s e c o n d ACK l i s t ma n a g e d b y
t h e a d j a c e n t n o d e a r e d e f i n e d a s a s e c o n d c ommo n l i s t ,
20 e a c h e n t r y i n t h e s e c o n d c ommo n l i s t i n c l u d e s d a t a s i z e
i n f o rma t i o n i n d i c a t i n g a d a t a s i z e o f a me s s a g e ,
wh e n t h e d a t a s i z e i n f o rma t i o n i n t h e s e c o n d c ommo n l i s t
i n d i c a t e s a v a l i d v a l u e , t h e e n t r y c o r r e s p o n d i n g t h e r e t o i s f o r a
me s s a g e s t o r e d i n a s e c o n d me s s a g e b u f f e r a r r a n g e d i n t h e a d j a c e n t
25 n o d e ,
wh e n t h e d a t a s i z e i n f o rma t i o n i n t h e s e c o n d c ommo n l i s t
i n d i c a t e s z e r o o r a n i n v a l i d v a l u e , t h e e n t r y c o r r e s p o n d i n g t h e r e t o i s
f o r a n ACK me s s a g e , a n d
t h e c ommu n i c a t i o n me t h o d f u r t h e r c omp r i s i n g d e l e t i n g , f r om t h e
30 f i r s t me s s a g e b u f f e r , a me s s a g e wh o s e d a t a s i z e i s i n d i c a t e d as z e r o o r
a n i n v a l i d v a l u e i n t h e s e c o n d c ommo n l i s t r e c e i v e d f r om t h e a d j a c e n t
n o d e .
2 8 . Th e c ommu n i c a t i o n me t h o d a c c o r d i n g t o a n y o n e o f Cl a ims
29
1 8 t o 2 7 , f u r t h e r c omp r i s i n g , i n r e s p o n s e t o r e c e i v i n g , t h r o u g h t h e
DTN, a f i r s t me s s a g e i n wh i c h t h e n o d e d e v i c e i s d e s i g n a t e d a s a f i n a l
d e s t i n a t i o n , a d d i n g a n ACK me s s a g e c o r r e s p o n d i n g t o t h e f i r s t me s s a g e
i n t h e f i r s t ACK l i s t .
5
2 9 . Th e c ommu n i c a t i o n me t h o d a c c o r d i n g t o a n y o n e o f Cl a ims
1 8 t o 2 8 , f u r t h e r c omp r i s i n g s e n d i n g t h e f i r s t ACK l i s t t o t h e a d j a c e n t
n o d e d u r i n g t h e c o n t a c t wi t h t h e a d j a c e n t n o d e .
10 3 0 . Th e c ommu n i c a t i o n me t h o d a c c o r d i n g t o a n y o n e o f Cl a ims
1 8 t o 2 9 , wh e r e i n t h e u p d a t i n g o f t h e f i r s t ACK l i s t i s p e r f o rme d b y
me r g i n g t h e f i r s t ACK l i s t wi t h t h e s e c o n d ACK l i s t r e c e i v e d f r om t h e
a d j a c e n t n o d e .
15 3 1 . Th e c ommu n i c a t i o n me t h o d a c c o r d i n g t o a n y o n e o f Cl a ims
1 8 t o 3 0 , wh e r e i n t h e u p d a t i n g o f t h e f i r s t s umma r y v e c t o r i s
p e r f o rme d b y e l imi n a t i n g , f r om t h e f i r s t s umma r y v e c t o r , a n e n t r y
r e g a r d i n g a me s s a g e h a v i n g t h e s ame i d e n t i f i e r a s t h a t o f t h e a l r e a d y -
d e l i v e r e d me s s a g e l i s t e d i n t h e s e c o n d ACK l i s t .
20
3 2 . Th e c ommu n i c a t i o n me t h o d a c c o r d i n g t o a n y o n e o f Cl a ims
1 8 t o 3 1 , f u r t h e r c omp r i s i n g u p d a t i n g t h e f i r s t me s s a g e b u f f e r b a s e d o n
t h e s e c o n d ACK l i s t .
25 3 3 . Th e c ommu n i c a t i o n me t h o d a c c o r d i n g t o Cl a im 3 2 , wh e r e i n
t h e u p d a t i n g o f t h e f i r s t me s s a g e b u f f e r i s p e r f o rme d b y d e l e t i n g , f r om
t h e f i r s t me s s a g e b u f f e r , a me s s a g e h a v i n g t h e s ame i d e n t i f i e r a s t h a t
o f t h e a l r e a d y - d e l i v e r e d me s s a g e l i s t e d i n t h e s e c o n d ACK l i s t .
30 3 4 . Th e c ommu n i c a t i o n me t h o d a c c o r d i n g t o a n y o n e o f Cl a ims
1 8 t o 3 3 , wh e r e i n e a c h o f t h e o n e o r mo r e ACK me s s a g e s i s g e n e r a t e d
b y t h e d e s t i n a t i o n n o d e .
3 5 . A n o n - t r a n s i t o r y c omp u t e r r e a d a b l e me d i um s t o r i n g a
30
p r o g r am f o r c a u s i n g a c omp u t e r t o p e r f o rm a c ommu n i c a t i o n me t h o d
a c c o r d i n g t o a n y o n e o f Cl a ims 1 8 t o 3 4 .
3 6 . A n o d e d e v i c e u s e d i n a Di s r u p t i o n /De l a y/Di s c o n n e c t
To l e r a n t Ne two r k (DTN) , t h e n o d e d e v i c e c omp r i s i n 5 g :
a c ommu n i c a t i o n u n i t c o n f i g u r e d t o c ommu n i c a t e wi t h a n
a d j a c e n t n o d e i n t h e DTN; a n d
a f i r s t me s s a g e b u f f e r c o n f i g u r e d t o s t o r e a p l u r a l i t y o f
me s s a g e s t r a n s f e r r e d t h r o u g h t h e DTN, wh e r e i n
10 t h e c ommu n i c a t i o n u n i t i s c o n f i g u r e d t o ma n a g e a f i r s t s umma r y
v e c t o r , a n d a l s o c o n f i g u r e d t o r e c e i v e a s e c o n d s umma r y v e c t o r
ma n a g e d b y t h e a d j a c e n t n o d e d u r i n g c o n t a c t wi t h t h e a d j a c e n t n o d e
a n d u p d a t e t h e f i r s t s umma r y v e c t o r a n d t h e f i r s t me s s a g e b u f f e r b a s e d
o n t h e s e c o n d s umma r y v e c t o r ,
15 t h e f i r s t s umma r y v e c t o r i n d i c a t e s o n e o r mo r e s t o r e d me s s a g e s
t h a t h a v e b e e n s t o r e d i n t h e f i r s t me s s a g e b u f f e r ,
t h e s e c o n d s umma r y v e c t o r i n d i c a t e s o n e o r mo r e s t o r e d
me s s a g e s t h a t h a v e b e e n s t o r e d i n a s e c o n d me s s a g e b u f f e r a r r a n g e d i n
t h e a d j a c e n t n o d e ,
20 e a c h e n t r y i n t h e f i r s t a n d s e c o n d s umma r y v e c t o r s i n c l u d e s d a t a
s i z e i n f o rma t i o n i n d i c a t i n g a d a t a s i z e o f a me s s a g e ,
wh e n t h e d a t a s i z e i n f o rma t i o n i n d i c a t e s a v a l i d v a l u e , t h e e n t r y
c o r r e s p o n d i n g t h e r e t o i s f o r a me s s a g e t h a t h a s b e e n s t o r e d i n t h e f i r s t
me s s a g e b u f f e r o r t h e s e c o n d me s s a g e b u f f e r ,
25 wh e n t h e d a t a s i z e i n f o rma t i o n i n d i c a t e s z e r o o r a n i n v a l i d v a l u e ,
t h e e n t r y c o r r e s p o n d i n g t h e r e t o i s f o r a n a l r e a d y - d e l i v e r e d me s s a g e
t h a t h a s a l r e a d y b e e n d e l i v e r e d t o a f i n a l d e s t i n a t i o n n o d e t h r o u g h t h e
DTN, a n d
t h e c ommu n i c a t i o n u n i t d e l e t e s , f r om t h e f i r s t me s s a g e b u f f e r ,
30 me s s a g e d a t a c o r r e s p o n d i n g t o t h e a l r e a d y - d e l i v e r e d me s s a g e wh o s e
d a t a s i z e i s i n d i c a t e d as z e r o o r a n i n v a l i d v a l u e i n t h e s e c o n d
s umma r y v e c t o r , a n d u p d a t e s t h e f i r s t s umma r y v e c t o r t o o v e rwr i t e t h e
d a t a s i z e i n f o rma t i o n i n t h e e n t r y , c o r r e s p o n d i n g t o t h e a l r e a d y -
d e l i v e r e d me s s a g e , wi t h z e r o o r a n i n v a l i d v a l u e .
31
3 7 . Th e n o d e d e v i c e a c c o r d i n g t o Cl a im 3 6 , wh e r e i n i n r e s p o n s e
t o o v e rwr i t i n g t h e d a t a s i z e i n f o rma t i o n i n an e n t r y o f t h e f i r s t
s umma r y v e c t o r wi t h z e r o o r a n i n v a l i d v a l u e , t h e c ommu n i c a t i o n u n i t
u p d a t e s o r r e s e t s a n e x p i r a t i o n t ime o f t h a t e n t r 5 y .