Erasure-Coding Based Routing for Opportunistic Networks - Revision history

Tkunze at 09:01, 20 October 2006

2006-10-20T09:01:59Z

← Older revision		Revision as of 09:01, 20 October 2006
Line 1:		Line 1:
	==Introduction==		==Introduction==
	Most current approaches for routing in DTN are based on sending multiple identical copies of packages over different paths. There is always a tradeoff between overhead and delay. The flooding algorithm, for example, has the best delay, but the worst overhead. The direct algorithm on the other side has the worst delay but the best overhead. We present an erasure coding based algorithm, that achieves a better worst-case delay performance than existing approaches ~~wiht~~ a fixed overhead.		Most current approaches for routing in DTN are based on sending multiple identical copies of packages over different paths. There is always a tradeoff between overhead and delay. The flooding algorithm, for example, has the best delay, but the worst overhead. The direct algorithm on the other side has the worst delay but the best overhead. We present an erasure coding based algorithm, that achieves a better worst-case delay performance than existing approaches with a fixed overhead.

	==Erasure Codes==		==Erasure Codes==
Line 6:		Line 6:

	==Erasure coding based routing(ec)==		==Erasure coding based routing(ec)==
	The ~~algorith~~ we present is a enhancement of the simple replication algorithm (srep). Is srep with replication factor <math>r</math>, the source sends <math>r</math> identical copies of the message over <math>r</math> contacts. This contacts may only send directly to the destination.		The algorithm we present is a enhancement of the simple replication algorithm (srep). Is srep with replication factor <math>r</math>, the source sends <math>r</math> identical copies of the message over <math>r</math> contacts. This contacts may only send directly to the destination.
	In the erasure ~~conding~~ based ~~algorith~~ (ec) the sender generates a large number ob codes blocks and distributes them over <math>k*r</math> relays, for some constant <math>k</math>. This uses <math>k</math> times more relays than srep, but each relay only carries <math>1/k</math> times data. So ec uses the same number of bytes as srep.		In the erasure coding based algorithm (ec) the sender generates a large number of codes blocks and distributes them over <math>k*r</math> relays, for some constant <math>k</math>. This uses <math>k</math> times more relays than srep, but each relay only carries <math>1/k</math> times data. So ec uses the same number of bytes as srep.
	Because <math>1/r</math> code blocks are needed to reconstruct the message, <math>k</math> relays have to deliver their data successfully.		Because <math>1/r</math> code blocks are needed to reconstruct the message, <math>k</math> relays have to deliver their data successfully.
	For <math>k=1</math> ec is the same as srep.		For <math>k=1</math> ec is the same as srep.

	==Benefits==		==Benefits==
	In srep <math>r</math> relays are used and one has to ~~succed~~. In es <math>k*r</math> relays are used but <math>k</math> relays must ~~succed~~ to reconstruct the message. If the number of low delay relays is ~~larget~~ than <math>k</math> ec will deliver the message with a lower delay than srep.If <math>k</math> is large, the delay distribution converges to a constant. Therefore ec has almost a constant delay.		In srep <math>r</math> relays are used and one has to succeed. In ec <math>k*r</math> relays are used but <math>k</math> relays must succeed to reconstruct the message. If the number of low delay relays is larger than <math>k</math> ec will deliver the message with a lower delay than srep.If <math>k</math> is large, the delay distribution converges to a constant. Therefore ec has almost a constant delay.

	==Material==		==Material==

Tkunze at 18:23, 19 October 2006

2006-10-19T18:23:49Z

← Older revision		Revision as of 18:23, 19 October 2006
Line 5:		Line 5:
	Erasure Codes convert a message into a large number of code blocks so, that any sufficient large subset of this blocks can be used to reconstruct the message. In more detail, if an erasure code has a message of size <math>M</math> and a replication factor <math>r</math> as input, it produces <math>M*r/b</math> equal sized code blocks of size <math>b</math>. Any <math>M/b</math> code blocks can be used to reconstruct the message. So only <math>1/r</math> code blocks are needed.		Erasure Codes convert a message into a large number of code blocks so, that any sufficient large subset of this blocks can be used to reconstruct the message. In more detail, if an erasure code has a message of size <math>M</math> and a replication factor <math>r</math> as input, it produces <math>M*r/b</math> equal sized code blocks of size <math>b</math>. Any <math>M/b</math> code blocks can be used to reconstruct the message. So only <math>1/r</math> code blocks are needed.

			==Erasure coding based routing(ec)==
			The algorith we present is a enhancement of the simple replication algorithm (srep). Is srep with replication factor <math>r</math>, the source sends <math>r</math> identical copies of the message over <math>r</math> contacts. This contacts may only send directly to the destination.
			In the erasure conding based algorith (ec) the sender generates a large number ob codes blocks and distributes them over <math>k*r</math> relays, for some constant <math>k</math>. This uses <math>k</math> times more relays than srep, but each relay only carries <math>1/k</math> times data. So ec uses the same number of bytes as srep.
			Because <math>1/r</math> code blocks are needed to reconstruct the message, <math>k</math> relays have to deliver their data successfully.
			For <math>k=1</math> ec is the same as srep.

			==Benefits==
			In srep <math>r</math> relays are used and one has to succed. In es <math>k*r</math> relays are used but <math>k</math> relays must succed to reconstruct the message. If the number of low delay relays is larget than <math>k</math> ec will deliver the message with a lower delay than srep.If <math>k</math> is large, the delay distribution converges to a constant. Therefore ec has almost a constant delay.

	==Material==		==Material==

Tkunze at 18:04, 19 October 2006

2006-10-19T18:04:50Z

← Older revision		Revision as of 18:04, 19 October 2006
Line 3:		Line 3:

	==Erasure Codes==		==Erasure Codes==
			Erasure Codes convert a message into a large number of code blocks so, that any sufficient large subset of this blocks can be used to reconstruct the message. In more detail, if an erasure code has a message of size <math>M</math> and a replication factor <math>r</math> as input, it produces <math>M*r/b</math> equal sized code blocks of size <math>b</math>. Any <math>M/b</math> code blocks can be used to reconstruct the message. So only <math>1/r</math> code blocks are needed.
	<math>\frac{1}{n} </math>


	==Material==		==Material==

Tkunze at 17:34, 19 October 2006

2006-10-19T17:34:15Z

← Older revision		Revision as of 17:34, 19 October 2006
Line 1:		Line 1:
			==Introduction==
			Most current approaches for routing in DTN are based on sending multiple identical copies of packages over different paths. There is always a tradeoff between overhead and delay. The flooding algorithm, for example, has the best delay, but the worst overhead. The direct algorithm on the other side has the worst delay but the best overhead. We present an erasure coding based algorithm, that achieves a better worst-case delay performance than existing approaches wiht a fixed overhead.

			==Erasure Codes==
			<math>\frac{1}{n} </math>

	==Material==		==Material==
	* the paper: [http://sarwww.informatik.hu-berlin.de/teaching/_previous-years/2006-s%20Interplanetary%20Internet%20Seminar/papers/af_Erasure-Coding%20Based%20Routing%20for%20Opportunistic%20Networks.pdf "Erasure-Coding Based Routing for Opportunistic Networks.pdf"]		* the paper: [http://sarwww.informatik.hu-berlin.de/teaching/_previous-years/2006-s%20Interplanetary%20Internet%20Seminar/papers/af_Erasure-Coding%20Based%20Routing%20for%20Opportunistic%20Networks.pdf "Erasure-Coding Based Routing for Opportunistic Networks.pdf"]

Tkunze at 17:13, 19 October 2006

2006-10-19T17:13:18Z

← Older revision		Revision as of 17:13, 19 October 2006
Line 1:		Line 1:

	==Material==		==Material==
	* the paper: [http://sarwww.informatik.hu-berlin.de/teaching/_previous-years/2006-s%20Interplanetary%20Internet%20Seminar/papers/af_Erasure-Coding%20Based%20Routing%20for%20Opportunistic%20Networks.pdf ]		* the paper: [http://sarwww.informatik.hu-berlin.de/teaching/_previous-years/2006-s%20Interplanetary%20Internet%20Seminar/papers/af_Erasure-Coding%20Based%20Routing%20for%20Opportunistic%20Networks.pdf "Erasure-Coding Based Routing for Opportunistic Networks.pdf"]

Tkunze at 17:12, 19 October 2006

2006-10-19T17:12:40Z

New page

==Material==
* the paper: [http://sarwww.informatik.hu-berlin.de/teaching/_previous-years/2006-s%20Interplanetary%20Internet%20Seminar/papers/af_Erasure-Coding%20Based%20Routing%20for%20Opportunistic%20Networks.pdf ]